【DFS, 二叉树】二叉树最大宽度

题目

662. 二叉树最大宽度

---

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

示例 3：

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示：

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

解题

方法一：DFS 二叉树

思路

众所周知，二叉树可以表示成一个数组，当某个节点的索引为 i 时，它的两个子节点的索引分别是 2 * i 和 2 * i + 1，我们可以利用这一点，对二叉树进行层序遍历。层序遍历时某层遇到的第一个节点一定是该层的最左节点，所以我们可以把一般层序遍历用到的存储节点的二维列表改为一个一维列表，其中每个元素代表当前层最左节点的索引值，那么只有在每次递归到新层的时候更新该列表，对于该层的其它节点，把它的索引与列表中该层的值作差加一表示该节点到最左节点的宽度，维护一个最大宽度。

注意：如果二叉树退化成链表，那么索引的值会呈指数级增长($2^n$)，这时索引的值会溢出整型(甚至长整型)范围，但是题目说了保证答案将会在32位带符号整数范围内，所以不用担心溢出，最后相减得到的宽度一定会在32位带符号整数范围内。Java 中的 int 在运算时溢出不会报错，但是 C++ 中有符号整型(int)会报错：runtime error: signed integer overflow: 1610612735 * 2 cannot be represented in type ‘int’，用无符号整型(unsigned int)溢出就不报错了。

代码

class Solution {
    List<Integer> lefts = new ArrayList<>();
    int max = 0;

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

    void dfs(TreeNode node, int level, int index) {
        if (node == null) return;
        if (level == lefts.size()) lefts.add(index);
        max = Math.max(max, index - lefts.get(level) + 1);
        dfs(node.left, level + 1, index * 2);
        dfs(node.right, level + 1, index * 2 + 1);
    }
}

class Solution {
    vector<unsigned int> lefts;
    unsigned int max_width;

public:
    void dfs(TreeNode* node, int level, unsigned int index) {
        if (!node) return;
        if (level == lefts.size()) lefts.push_back(index);
        max_width = max(max_width, index - lefts[level] + 1);
        dfs(node->left, level + 1, index * 2);
        dfs(node->right, level + 1, index * 2 + 1);
    }

    int widthOfBinaryTree(TreeNode* root) {
        dfs(root, 0, 1);
        return max_width;
    }
};