LeetCode 513. Find Bottom Left Tree Value
由 瞳人
发布于 March 2, 2017, 8:16 p.m.
0 个评论
题目
513. Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
1 2 3 4 5 6 7 8 | Input:
2
/ \
1 3
Output:
1
|
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12 | Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
|
Note: You may assume the tree (i.e., the given root node) is not NULL.
解法
我一开始很自然地就想到了 BFS 算法，和之前 leetcode 515 中最后提到的 StefanPochmann 算法一样。
1 2 3 4 5 6 7 8 9 10 11 12 13 | def findBottomLeftValue(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return -1 row = [root] res = root.val while any(row): res = row[0].val row = [kid for node in row for kid in (node.left, node.right) if kid] return res |
然后我在讨论区又看到了这哥们惊人的解答，从右至左的 BFS，这样只需要遍历完树，最后一个结点即为所求结点。注意，当 filter 的第一个参数为 None 时，返回第二个参数中为 True 的值，也即非空子结点。
1 2 3 4 5 | def findBottomLeftValue(self, root): queue = [root] for node in queue: queue += filter(None, (node.right, node.left)) return node.val |
0 Comments