LeetCode——662.二叉树最大宽度

大佬，牛！！！

• 题目：给你一个数组，然后问他的宽度是多少。至于宽度的定义，是每一层宽度的最大值。至于每一层的宽度，就是左边的节点编号减去右边的节点编号+1。注意这个编号是按照满二叉树进行的。
• 我的思路：我们来想把这个完全二叉树先构造出来，然后发现超时了。一时也没找到更好的思路。于是看了一下大佬的讲解。
• 大佬的思路：大佬有两种思路，广度优先和深度优先。
  • 广度优先：我测试了一下，广度优先的速度稍微慢一点。但是里面有一个java的Pair类，我之前没有用过，感觉这次也是学到了。其实就是类似map。按照层序遍历，然后key是树的节点。value是对应的idx。注意idx的计算规则，下一层左节点是上一层2，右节点是2再+1。然后每一层都找到这一层的idx最大值和最小值进行相减。
  • 深度优先：深度优先还是有点绕的，首先我们每一层都会传递一个idx，然后一次递归就是找以这个idx节点为最右侧的节点时，树的宽度。那么就是idx-这一层最左侧的节点下标。但是你还要考虑他的左子树和右子树。所以就是左子树，右子树，以及自己为最右侧时，这三个中的最大值。至于这个最左侧的值，我们可以用一个map进行保存，因为遍历的时候，都是先遍历左边，所以我们可以putIfAbsent，放入当前的idx，如果这一层已经有了，那就不放了。
• 技巧：二叉树的宽度，二叉树的下标

java代码——广度优先

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int res = 1;
        List<Pair<TreeNode, Integer>> arr = new ArrayList<Pair<TreeNode, Integer>>();
        arr.add(new Pair<TreeNode, Integer>(root, 1));
        while (!arr.isEmpty()) {
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<Pair<TreeNode, Integer>>();
            for (Pair<TreeNode, Integer> pair : arr) {
                TreeNode node = pair.getKey();
                int index = pair.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));
                }
            }
            res = Math.max(res, arr.get(arr.size() - 1).getValue() - arr.get(0).getValue() + 1);
            arr = tmp;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

java代码——深度优先

class Solution {
    Map<Integer, Integer> levelMin = new HashMap<Integer, Integer>();

    public int widthOfBinaryTree(TreeNode root) {
        return dfs(root, 1, 1);
    }

    public int dfs(TreeNode node, int depth, int index) {
        if (node == null) {
            return 0;
        }
        levelMin.putIfAbsent(depth, index);
        return Math.max(index - levelMin.get(depth) + 1, Math.max(dfs(node.left, depth + 1, index * 2), dfs(node.right, depth + 1, index * 2 + 1)));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 总结：我觉得题目还是挺难的，我之前一位层序白能力比较简单，是我草率了，对不起，我错了。最后附上大佬链接。