[LeetCode]513. Find Bottom Left

题目

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.

难度

Medium

方法

通过使用队列后续遍历二叉树，队列中的最后一个节点即为二叉树最后一行的最左节点

python代码

from Queue import Queue

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 = Queue()
        queue.put(root)
        node = None
        while not queue.empty():
            node = queue.get()
            if node.right:
                queue.put(node.right)
            if node.left:
                queue.put(node.left)

        return node.val


root = TreeNode(2)
left = TreeNode(1)
right = TreeNode(3)
root.left = left
root.right = right
Solution().findBottomLeftValue(root) == 1

root = TreeNode(1)
node1_1 = TreeNode(2)
node1_2 = TreeNode(3)
node2_1 = TreeNode(4)
node2_2 = TreeNode(5)
node2_3 = TreeNode(6)
node3_1 = TreeNode(7)
root.left = node1_1
root.right = node1_2
node1_1.left = node2_1
node1_2.left = node2_2
node1_2.right = node2_3
node2_2.left = node3_1
Solution().findBottomLeftValue(root) == 7