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.

思路

利用队列进行树的层次遍历，亦即广度优先搜索。层次遍历时右子树先入栈，接着左子树入栈。由此可以找到最后一层最左侧的元素。另外，因为我们不需要知道遍历到了第几层，所以不需要加入空节点。这大大简化了层次遍历的过程。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import Queue
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        a = Queue.Queue()
        if (root):
            a.put(root)
        ans = 0
        while(not a.empty()):
            cur = a.get()
            if (cur):
                ans = cur.val
                a.put(cur.right)
                a.put(cur.left)
        return ans