题解 | #二叉树的最大宽度#

二叉树的最大宽度

http://www.nowcoder.com/practice/0975d62a307549cea32f353f354a7377

题目分析

题目给出了我们一棵二叉树，其根节点作为输入

题目要求我们返回该二叉树中最大的宽度，即返回二叉树某一层中，从最左边的节点到最右边的节点最远的距离（包括它们之间的空节点也要计入距离）

方法一：DFS深度优先遍历

实现思路
- 我们将根节点root编号(pos)记为1，因此在该树中，对于任何一个节点node，我们将其和子节点的编号设置为
$pos(node.left) = pos(node) × 2\\ pos(node.right) = pos(node)×2+1$
- 这样就能保证我们对于树中的空节点的位置都有一个编号，便于我们计算每层的宽度
- 然后我们可以利用深度优先遍历，维护两个数据结构left[]和right[]和层值level
- 在DFS过程中，如果该层是第一次遍历到的，我们就将该层遍历到的第一个节点编号计入，即left[level], right[level] = pos, pos
- 在DFS过程中，又经过了该层的时候，则修改right[level] = pos，因为再次经过该层的节点时，该节点都有可能是该层最后一个节点，所以其编号需要重新记录一次
- 每次更新left[],right[]后，都需要计算一次mx，即计算一次最大宽度是否更新了，最终返回mx即可

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    mx = 0
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        def dfs(root, level, pos, left, right):
            if root == None:
                return
            if len(left) == level:                                    # 第一次到达新的level时候，记录的点就是做左边的点
                left.append(pos)
                right.append(pos)
            else:
                right[level] = pos                                    # 以后的每一次到达某level的时候，都可能是该level最右边的点
            dfs(root.left, level+1, pos*2, left, right)
            dfs(root.right, level+1, pos*2+1, left, right)
            self.mx = max(self.mx, right[level] - left[level] + 1)
        dfs(root, 0, 1, [], [])
        return self.mx

复杂度分析

时间复杂度： $O (n)$ ，由于对所有的节点遍历了一次，所以时间代价与节点数量呈线性关系
空间复杂度：最坏情况为 $O (n)$ ，最好情况下递归栈的深度、 $l e f t []$ ， $r i g h t []$ 结构的空间代价都是与节点数量呈对数关系的，最坏情况下树退化成一条链表，空间代价为 $O (n)$

方法二：层序遍历

实现思路
- 将递归的思路转化为层序的思路
- 即维护一个队列，按照每层的节点数量为一个循环进行操作
- 队列逻辑是
  - 循环首先获取队列的大小n即一个计数器，然后在循环中逐个获取队首节点并出队，并对计数器n作减一操作。
  - 循环中，如果该节点是该层首个节点，则记录left，如果是该层的最后一个节点，则记录right。
  - 对于所有出队节点，都需要将其非空的左右子节点入队，并将编号按照方法一中的方式维护
  - 每一层循环结束后要计算该层的宽度right-left+1，并与最大宽度比较记录mx = max(mx, right-left+1)
- 最后返回最大宽度mx

alt

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
import queue
class Solution:
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        q = queue.Queue()
        q.put((root, 1))            # 根节点入队
        mx = 0
        while not q.empty():	
            n = q.qsize()
            num = q.qsize()
            left, right = 0, 0
            while n:
                node, v = q.get()
                if n == num:        # 记录最左边节点的标记
                    left = v
                if n == 1:          # 记录最右边节点的标记
                    right = v
                if node.left:
                    q.put((node.left, 2*v))
                if node.right:
                    q.put((node.right, 2*v+1))
                n -= 1
            mx = max(mx, right-left+1)
        return mx