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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

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:
class Solution:

	def findBottomLeftValue(self, root):
		dealArr = []
		indexNum = self.dealTree(root, dealArr, 0)
		return dealArr[indexNum - 1][0]

	def dealTree(self, root, dealArr, indexNum):
		if root == None:
			return indexNum
		if len(dealArr) <= indexNum:
			dealArr.append([])
		dealArr[indexNum].append(root.val)
		indexNum1 = self.dealTree(root.left, dealArr, indexNum + 1)
		indexNum2 = self.dealTree(root.right, dealArr, indexNum + 1)
		return max(indexNum1, indexNum2)


class Solution:

	def findBottomLeftValue(self, root):
		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)