513.md

513. Find Bottom Left Tree Value

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.

my thoughts:

1. traversal from left to right and find all leaves, record leaf and its depth (+1 when calling children);
go through leaves from left to right, find the first deepest leaf, and return.
O(n)

my solution:

# 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
        """
        self.l = []
        self.d = []
        def depleaf(root, d):
            if not root:
                return 
            if not root.left and not root.right:
                self.l.append(root.val)
                self.d.append(d)
                return 
            depleaf(root.left, d+1)
            depleaf(root.right, d+1)
        depleaf(root, 1)
        p1 = p2 = 0
        while p2<len(self.d):
            if self.d[p2]>self.d[p1]:
                p1 = p2
            p2 = p2 + 1
        return self.l[p1]

my comments:

solution accepted, 62ms run time

from other ppl's solution:

1. peel the tree like an onion, very nice, 56ms:
* my understanding: q is the core, q2 is the next layer, while till no next layer, now q2 is the deepest leaves, find the first one.
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return None
        q = [root]
        while q:
            q2 = []
            for node in q:
                if node.left:
                    q2.append(node.left)
                if node.right:
                    q2.append(node.right)
            if not q2:
                return q[0].val
            q = q2