Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
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.
Solutions
1. 中序遍历
主要是想法，中序遍历树，那么最后一层第一个访问到的肯定是要求的结果。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorder(self, root, level):
if not root:
return
self.inorder(root.left, level+1)
if self.max_depth < level:
self.res, self.max_depth = root.val, level
self.inorder(root.right, level+1)
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res, self.max_depth = 0, -1
self.inorder(root, 0)
return self.res
# Runtime: 44 ms, faster than 12.18% of Python online submissions for Find Bottom Left Tree Value.
# Memory Usage: 16.9 MB, less than 20.00% of Python online submissions for Find Bottom Left Tree Value.
2. BFS-从右往左遍历
BFS 从右往左遍历的话，最后一个结点就是想要的结果。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
queue = [root]
while queue:
node = queue.pop()
if node.right:
queue.insert(0, node.right)
if node.left:
queue.insert(0, node.left)
return node.val
# Runtime: 40 ms, faster than 27.18% of Python online submissions for Find Bottom Left Tree Value.
# Memory Usage: 16.2 MB, less than 60.00% of Python online submissions for Find Bottom Left Tree Value.