广度优先遍历

DFS（深度优先搜索）和 BFS（广度优先搜索）的区别

如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。例如：「层序遍历」、「最短路径」。
DFS 遍历使用递归：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS 遍历使用队列数据结构：

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

思路：
BFS 和 DFS 都可以。
DFS，关键点是设置 level 参数，比较当前层级 level 和 结果集 res 的长度，如果 level 大于等于结果集 res 的长度，则说明当前层级遍历已经结束，需要开始遍历下一层级。
BFS，关键点是在队列循环的过程中，获取当前队列的长度，然后进行二级循环，这样二级循环中添加的值都来自同一层级的结点，并把下一层的结点加入到队列末尾。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, root, 0);
        return res;
    }
    private void dfs(List<List<Integer>> res, TreeNode node, int level) {
        if (node == null) {
            return;
        }
        List<Integer> cur;
        if (level >= res.size()) {
            cur = new ArrayList<>();
            cur.add(node.val);
            res.add(cur);
        } else {
            cur = res.get(level);
            cur.add(node.val);
        }
        dfs(res, node.left, level+1);
        dfs(res, node.right, level+1);
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(new ArrayList<>(temp));
        }
        return res;
    }
}

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

思路：
BFS，将完全平方数加入队列，逐渐减小 head 的值，直到满足 j j == head。
动态规划，dp[i] 的值为 dp[i-jj]+1 中最小的那个。

class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        boolean[] visited = new boolean[n + 1];
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int head = queue.poll();
                for (int j = 1; j * j <= head; j++) {
                    if (j * j == head) {
                        return step;
                    }
                    int next = head - j * j;
                    if (!visited[next]) {
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }
}

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int res = Integer.MAX_VALUE;
            for (int j = 1; i - j * j >= 0; j++) {
                res = Math.min(1 + dp[i - j * j], res);
            }
            dp[i] = res;
        }

        return dp[n];
    }
}

练习：

662. 二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

思路：

/**
 * 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) {
        if (root == null) return 0;
        Queue<TreeNode> s = new LinkedList<>();
        Queue<Integer> q = new LinkedList<>();
        s.add(root);
        q.add(1);
        int max = 1;
        while (s.size() != 0) {
            int len = s.size();
            int start = q.peek();
            for (int i = 0; i < len; i++) {
                TreeNode t = s.poll();
                int index = q.poll();
                if (i == len - 1) max = Math.max(max, index - start + 1);
                if (t.left != null) {
                    s.offer(t.left);
                    q.offer(index * 2 - 1);
                }
                if (t.right != null) {
                    s.offer(t.right);
                    q.offer(index * 2);
                }
            }
        }
        return max;
    }
}

993. 二叉树的堂兄弟节点