Posted on 2023-04-20 18:45
Uriel 閱讀(63)
評論(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