题目: 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
来源: https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
法一: 自己的代码 超时
思路: 利用层序遍历,对空节点用1代替,显然上一层的一个1对应下一层的两个1,每append一个非空节点都记录一下list的长度,最后再推算出该层的宽度.
class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: queue = [] queue_next = [] wide = [] if root is None: return 0 queue.append(root) # 初始值设置为1,用于记录append一个非空节点后,list的长度 feikong_index = [1] # 利用层序遍历 while queue: queue_next = queue queue = [] l = len(feikong_index) # 求每一层树的宽度 if l > 1: wide.append(feikong_index[-1] - feikong_index[0] + 1) # 利用切片把左右两边的空节点去掉 queue_next = queue_next[feikong_index[0]-1 : feikong_index[-1]] elif l == 1: wide.append(1) queue_next = [queue_next[feikong_index[0]-1]] else: # 如果feikong_index长度为0,说明全为空节点, queue_next = [] feikong_index = [] while queue_next: a = queue_next.pop(0) # 如果是整型,说明为1,说明为空节点,则下一层有两个空节点,所以append两次1,进行下一次循环 if type(a) is int: queue.append(1) queue.append(1) continue # 如果左节点非空,记录队列的长度,最后一次记录的长度和第一次记录的长度之差再加1即为该层二叉树去掉左右空节点的长度 if a.left: queue.append(a.left) feikong_index.append(len(queue)) else: queue.append(1) if a.right: queue.append(a.right) feikong_index.append(len(queue)) else: queue.append(1) return max(wide)
法二: 官方解法
思路: (广度优先)方法很巧妙,类似于奇偶数列通项公式的求法,对每一个非空节点的深度和项数n都做记录,无需管空节点.
这类题关键是先数学演算,数学演算实现的方法越简单,代码也越易实现.
# 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): 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)) # print(depth+1, pos*2) print(depth,pos) queue.append((node.right, depth+1, pos*2 + 1)) # 如果当前深度和正在遍历的深度不相等,则将cur_depth变为正在遍历的深度 # 两个不相等时,说明到下一层了,更新cur_depth if cur_depth != depth: cur_depth = depth # left记录的是每一层最左边的第一个非空节点的位置 left = pos # 每次都计算一次看是否为最大值 ans = max(pos - left + 1, ans) print('ans is:', pos,ans) return ans if __name__ == '__main__': duixiang = Solution() def list_to_binarytree(a): if a[0] is None: return [] stack = [] root = TreeNode(a.pop(0)) stack.append(root) while a: # 一层一层的遍历 stack_next = stack stack = [] # a有可能提前变为[],这时直接结束内循环 while stack_next and a: # 注意这里的b不能是空对象的地址,否则会出错 b = stack_next.pop(0) # 为了保证结构的统一特别引入了555,stack中555表示这里是一个空节点, # stack中只有两种值一种是555,另一种是节点的地址 # 上一层的空节点对应下一层a中的两个None,依次弹出 if b == 555: a.pop(0) a.pop(0) continue # 如果某个节点为None,则将其地址标记为555 if a[0] == None: a.pop(0) stack.append(555) else: b.left = TreeNode(a.pop(0)) stack.append(b.left) if a[0] == None: a.pop(0) stack.append(555) else: b.right = TreeNode(a.pop(0)) stack.append(b.right) return root a = [1, 3,2, 5,3,None,9] # a = [1,2,3,4,None,None,5,6,7,None,None,None,None,8,9] # a = [1, 2, None, 4, 3, None, 5] a = duixiang.widthOfBinaryTree(list_to_binarytree(a)) print(a)
思路: (深度优先)利用递归和setdefault的特性,实现对每一层最左边节点位置的记录.
总结: 1 凡是深度优先的都可以用宽度优先,反之亦然.
2 二叉树的题都可以用递归和迭代两种方法实现,这道题提供了一种非常好的节点位置记录方法.
# 递归解法,这里可以看做是前序遍历 class Solution(object): def widthOfBinaryTree(self, root): self.ans = 0 left = {} def dfs(node, depth = 0, pos = 0): if node: # setdefault只记录第一次出现的k-v对,之后出现的无法覆盖,所以left中记录的是每一层最左边节点的位置 left.setdefault(depth, pos) self.ans = max(self.ans, pos - left[depth] + 1) dfs(node.left, depth + 1, pos * 2) dfs(node.right, depth + 1, pos * 2 + 1) dfs(root) return self.ans