【leetcode题解】宽搜（BFS）

目录

 宽搜（BFS）

N 叉树的层序遍历

二叉树的锯齿形层序遍历

二叉树最大宽度

在每个树行中找最大值

 宽搜（BFS）

N 叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null)
            return ret;
        Queue<Node> q = new LinkedList<>();// 使用队列
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();// 统计本层的节点信息
            for (int i = 0; i < sz; i++) {
                Node t = q.poll();
                tmp.add(t.val);
                for (Node child : t.children) {
                    if (child != null) {
                        q.add(child);// 孩子入队
                    }
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
}

二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

解法：层序遍历

增加一个标记位，让偶数行的信息逆序即可 Collections.reverse();

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();// 用来返回结果
        if (root == null)
            return ret;// 判空
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);// 用来获取二叉树中元素
        int level = 1;// 标记是否是偶数行
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new LinkedList<>();// 用来记录每一行结果
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.poll();
                tmp.add(t.val);
                if (t.left != null)
                    q.add(t.left);
                if (t.right != null)
                    q.add(t.right);
            }
            // 判断是否逆序
            if (level % 2 == 0)
                Collections.reverse(tmp);
            ret.add(tmp);
            level++;
        }
        return ret;
    }
}

二叉树最大宽度

662. 二叉树最大宽度 - 力扣（LeetCode）

解法一：硬补 -> 超时、内存可能不够

解法二：利用数组存储二叉树的方式（堆），给节点编号

细节：①用数组来实现队列，这样队头队尾比较好找

②下标可能溢出。相减之后，即使溢出，结果也是正确的（数据存储是环形的，距离不会溢出）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();// 用数组模拟队列
        q.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0;// 记录最终结果
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> t1 = q.get(0);// 得到队头
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);// 得到队尾
            ret = Math.max(t2.getValue() - t1.getValue() + 1, ret);
            // 下一层进队
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();
                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
                }
            }
            q = tmp;
        }
        return ret;
    }
}

在每个树行中找最大值

515. 在每个树行中找最大值 - 力扣（LeetCode）

解法：利用层序遍历，统计出每一层最大值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null)
            return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            int tmp = Integer.MIN_VALUE;
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.poll();
                tmp = Math.max(tmp, t.val);
                if (t.left != null)
                    q.add(t.left);
                if (t.right != null)
                    q.add(t.right);
            }
            ret.add(tmp);
        }
        return ret;
    }
}