题目描述

算法

(DFS\BFS) $O(n)$

这道题目只需要对二叉树进行一次遍历即可. (DFS/BFS都可以)
首先你要明确距离的定义, 是这一层两端的节点在对应的满二叉树中的距离. 我们可以在遍历的过程中维护每个节点在满二叉树的这一层中的下标:
如果一个节点的下标是 idx, 那么它的左子节点的下标就是 $idx * 2$, 它的右子节点的下标就是 $idx * 2 + 1$.
我们记录下每一层出现的最大的和最小的下标即可得到这一层的宽度, 然后在所有层的宽度中取最大值即可.
(这道题目节点的 val 属性是没有用的)

Java 代码

class Solution {
    private int max;
    public int widthOfBinaryTree(TreeNode root) {
        max = 0;
        List<Integer> left = new ArrayList();
        dfs(root, 0, 0, left);
        return max;
    }

    public void dfs(TreeNode root, int depth, int x, List<Integer> left) {
        if (root == null) return;
        if (left.size() <= depth) left.add(x);
        int width = x - left.get(depth) + 1;
        max = Math.max(max, width);
        dfs(root.left, depth + 1, 2 * x, left);
        dfs(root.right, depth + 1, 2 * x + 1, left);
    }
}

Python 代码

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        queue = [(root, 0, 0)]
        cur_depth = left = ans = 0
        for node, depth, pos in queue:
            if node:
                queue.append((node.left, depth+1, pos*2))
                queue.append((node.right, depth+1, pos*2 + 1))
                if cur_depth != depth:
                    cur_depth = depth
                    left = pos
                ans = max(pos - left + 1, ans)

        return ans