跳转至

LeetCode: 662. 二叉树最大宽度

1、题目描述

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

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

示例 1:

输入: 

       1
     /   \
    3     2
   / \     \  
  5   3     9

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入: 

      1
     /  
    3    
   / \       
  5   3

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入: 

      1
     / \
    3   2 
   /        
  5

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入: 

      1
     / \
    3   2
   /     \  
  5       9 
 /         \
6           7

输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

  • 注意: 答案在32位有符号整数的表示范围内。

2、解题思路

  • 层次遍历
  • 在层次遍历的同时，保存节点的索引号
         1
      2     3
    4   5 6   7

如上，左子节点的索引号为当前节点索引号的2*index，右子节点为2*index+1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        res = 1
        temp = [(root, 1)]

        while temp:
            _, left = temp[0]
            _, right = temp[-1]
            res = max(res, right - left + 1)
            t = []
            for node, index in temp:
                if node.left:
                    t.append((node.left, 2 * index))
                if node.right:
                    t.append((node.right, 2 * index + 1))
            temp = t

        return res