LeetCode 515. Find Largest Value in Each Tree Row
由 瞳人
发布于 March 1, 2017, 8:30 p.m.
0 个评论
原题
You need to find the largest value in each row of a binary tree.
即，找出树的每一层中间的最大值。
Example:
1 2 3 4 5 6 7 | Input:
1
/ \
3 2
/ \ \
5 3 9
Output: [1, 3, 9]
|
解法
我一开始写了个非递归的 BFS 算法，用一个特殊的 sep 来分隔各行，以便来计算各行的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | def largestValues(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] # Use a special node to separate rows sep = TreeNode(-1) queue = [sep, root] results = [] row = -1 while len(queue) > 1: node = queue[0] if node is sep: # Come to a new row row += 1 # Children of last row have been enqueued, # so we mark next row's end queue.append(sep) del queue[0] node = queue[0] results.append(node.val) else: results[row] = max(node.val, results[row]) # Enqueue children if it has if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) del queue[0] return results |
然后看见了讨论区的基于递归的算法，答案来自 zhongyuan9817 。其中增加一个调用参数，来记录访问结点的层数，以便与相同层数的结点比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 | def largestValues(self, root): self.res = [] self.helper(root, 0) return self.res def helper(self, root, level): if not root: return if level >= len(self.res): self.res += [root.val] else: self.res[level] = max(root.val, self.res[level]) self.helper(root.left, level + 1) self.helper(root.right, level + 1) |
讨论区中，看见了让我觉得叹为观止的代码，来自于 StefanPochmann。
1 2 3 4 5 6 7 | def largestValues(self, root): maxes = [] row = [root] while any(row): maxes.append(max(node.val for node in row)) row = [kid for node in row for kid in (node.left, node.right) if kid] return maxes |
其中值得学习的是 Python 中 list 映射（list comprehensions）中两个 for 的使用，max参数中的生成器操作，以及 any 的使用。关于这个两个 for 循环的解释，可以参考 YJL1228 的解释。
1 2 3 4 5 6 7 | row = [a,b,c,d...] xxx = [] for node in row: for kid in (node.left, node.right): if kid: xxx += kid, row = xxx |
0 Comments