Posted on 2023-04-20 18:45
Uriel 阅读(40)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
数据结构 、
闲来无事重切Leet Code
判断二叉树所有层中同一层左右节点宽度最大是多少，BFS，每次处理一层并且求宽度，多开了一个deque来存每个进队的节点的编号，可以把编号和node节点信息合并，用一个新的node class保存，但似乎用两个deque更省内存
1 #662
2 #Runtime: 28 ms (Beats 72.48%)
3 #Memory: 14.9 MB (Beats 82.57%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def widthOfBinaryTree(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 q = deque([root])
18 q_idx = deque([1])
19 ans = 0
20 while q:
21 s = len(q)
22 for i in range(s):
23 node = q.popleft()
24 x = q_idx.popleft()
25 if i == 0:
26 tp_min = x
27 if i == s - 1:
28 tp_max = x
29 if node.left:
30 q.append(node.left)
31 q_idx.append(2 * x - 1)
32 if node.right:
33 q.append(node.right)
34 q_idx.append(2 * x)
35 ans = max(ans, tp_max - tp_min + 1)
36 return ans