Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
判断二叉树所有层中同一层左右节点宽度最大是多少,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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理