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.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from collections import deque
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.queue = deque([])
         self.queue.append(root)
         return self.bfs()
 
     def bfs(self):
         while len(self.queue):
             node = self.queue.popleft()
             if node.right:
                 self.queue.append(node.right)
             if node.left:
                 self.queue.append(node.left)
         return node.val
         

class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         dealArr = []
         indexNum = self.dealTree(root, dealArr, 0)
         # print(indexNum, dealArr[indexNum - 1][0])
         return dealArr[indexNum - 1][0]
     def dealTree(self, root, dealArr, indexNum):
         if root == None:
             return indexNum
         # if not dealArr[indexNum]:
         if len(dealArr) <= indexNum :
             dealArr.append([])
         dealArr[indexNum].append(root.val)
         # print(root.val, dealArr, len(dealArr))
         indexNum1 = self.dealTree(root.left, dealArr, indexNum + 1)
         indexNum2 = self.dealTree(root.right, dealArr, indexNum + 1)
         return max(indexNum1, indexNum2)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         
         leftmost = []
         
         def recurse(node, path):
             nonlocal leftmost
             
             if node is None:
                 return
             
             if len(path) > len(leftmost):
                 leftmost = path
                 
             if 0 < len(path) == len(leftmost):
                 if int(''.join(path), 2) < int(''.join(leftmost), 2):
                     leftmost = path
             
             recurse(node.left, path + ['0'])
             recurse(node.right, path + ['1'])
 
         recurse(root, [])
             
         node = root
         while leftmost:
             if leftmost.pop(0) == '0':
                 node = node.left
             else:
                 node = node.right
                 
         return node.val

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         last = [root]
         now = []
         for node in last:
             if node.left:
                 now.append(node.left)
             if node.right:
                 now.append(node.right)
         
         while now:
             last, now = now, []
             for node in last:
                 if node.left:
                     now.append(node.left)
                 if node.right:
                     now.append(node.right)   
         
         return last[0].val

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         q = [root]
         while any(q):
             res = q[0]
             q = [kid for node in q for kid in (node.left, node.right) if kid]
         return res.val

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         q = [(root,1)]
         cur = (root,1)
         while (q!=[]):
             node,depth = q.pop(0)
             if depth > cur[1]:
                 cur = (node,depth)
             if node.left != None:
                 q.append((node.left,depth + 1))
             if node.right != None:
                 q.append((node.right,depth + 1))
         return cur[0].val

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         queue=[root]
         
         while queue:
             new_queue=[]
             for node in queue:
                 if node.left:
                     new_queue.append(node.left)
                 if node.right:
                     new_queue.append(node.right)
             if new_queue==[]:
                 return queue[0].val
             queue=new_queue

class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.maxHeight = 0
         self.leftNode = None
         self.findNode(root, 1)
         return self.leftNode
 
     def findNode(self, root, height):
         if not root:
             return
         if height > self.maxHeight:
             self.leftNode = root.val
             self.maxHeight = height
         self.findNode(root.left, height+1)
         self.findNode(root.right, height+1)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         if root==None:
             return []
         if root.left == None and root.right == None:
             return root.val
         queue = [root]
         answer = [root.val]
         while queue != []:
             temp = []
             for curr in queue:
                 if curr.left != None and curr.right != None:
                     temp.append(curr.left.val) 
                     temp.append(curr.right.val)
                 elif curr.left == None and curr.right!=None:
                     temp.append(curr.right.val)
                 elif curr.right == None and curr.left!=None:
                     temp.append(curr.left.val)
             if temp:
                 answer.append(temp)
             nt = []
             for curr in queue:
                 if curr.left != None and curr.right != None: 
                     nt.append(curr.left)
                     nt.append(curr.right)
                 elif curr.left == None and curr.right!=None:
                     nt.append(curr.right)
                 elif curr.right == None and curr.left!=None:
                     nt.append(curr.left)
             queue = nt
         if answer[-1] != None:
             return answer[-1][0]

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         queue = [root]
         i = 0
         while i < len(queue):
             queue += filter(lambda node: bool(node), [queue[i].right, queue[i].left])
             i += 1
 
         return queue[-1].val

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         q = [root]
         lastRow = [root]
         # store = [[root]]
 
         while len(q) > 0:
             row = []
     
             while len(q) > 0:
                 popped = q[0]
                 q = q[1:]
             
                 if popped.left:
                     row.append(popped.left)
                 if popped.right:
                     row.append(popped.right)
             
             q = row
             if len(row) > 0:
                 # store.append(row)
                 lastRow = row
         return lastRow[0].val
         # return store[-1][0].val
 


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         q = [root]
         lastRow = [root]
         # store = [[root]]
 
         while len(q) > 0:
             row = []
     
             while len(q) > 0:
                 popped = q[0]
                 q = q[1:]
             
                 if popped.left:
                     row.append(popped.left)
                 if popped.right:
                     row.append(popped.right)
             
             q = row
             if len(row) > 0:
                 # store.append(row)
                 lastRow = row
         return lastRow[0].val
         # return store[-1][0].val
 


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         r=[]
         l=[]
         rorl=[]
         def record(root,level,rl):
             if not root:
                 return
             r.append(root.val)
             l.append(level)
             rorl.append(rl)
             record(root.left,level+1,rl-1)
             record(root.right,level+1,rl+1)
         record(root,0,0)
         lastlevel=max(l)
         index=[]
         for i in range(len(l)):
             if l[i]==lastlevel:
                 index.append(i)
         tmp=r[index[0]]
         rr=rorl[index[0]]
         for ind in index:
             if rorl[ind]<rr:
                 rr=rorl[ind]
                 tmp=r[ind]
         return tmp
             
             
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findBottomLeftValue(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         # nonlocal lowest
         lowest = {'depth':-1, 'horz':0, 'value':0}
         
         def check_and_update_lowest(depth, horz, value):
             if (depth > lowest['depth']) or (depth == lowest['depth'] and horz < lowest['horz']):
                 lowest['depth'] = depth
                 lowest['horz'] = horz
                 lowest['value'] = value
             
                 
         
         def deeper(node, level= 0, horz = 0):
             
             if node is None:
                 return
             
             if not(node.left or node.right):
                 check_and_update_lowest(level, horz, node.val)
                 return
             
             deeper(node.left,level+1, horz-1)
             deeper(node.right,level+1, horz+1)
             
         deeper(root)
         
         return lowest['value']