给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

2
   / 
  1   3

输出: 1

示例 2:

输入:

1
   / 
  2   3
 /   / 
4   5   6
   /
  7

输出: 7

注意: 您可以假设树（即给定的根节点）不为 NULL。

方法一：迭代法

思路：

1. 在层次遍历的过程中，每次记录每一层的第一个元素。遍历完记录的则是答案。
2. 外层循环处理每一层，内层循环处理每一层的数据。

class Solution {
          
   
    public int findBottomLeftValue(TreeNode root) {
          
   
        // 1. 创建队列和一个结果变量用来存储每一行最左边的值
        Queue<TreeNode> queue = new LinkedList<>();
        int ans = 0;

        // 2. 根节点入队
        queue.offer(root);

        // 3. 遍历每一层的数据
        while(!queue.isEmpty()) {
          
   
            int size = queue.size();
            ans = queue.peek().val; // 存储每一层的第一个元素

            while(size > 0) {
          
   
                TreeNode node = queue.poll();
                //判断是否有左节点
                if (node.left != null) {
          
   
                    queue.offer(node.left);
                }
                //判断是否有右节点
                if (node.right != null) {
          
   
                    queue.offer(node.right);
                }
                size--;
            }
        }
        return ans;
    }
}

方法二：递归

思路：

1. 采用中序遍历，记录最深处，最左边的元素。
2. 递归的过程中，深度加深了，就需要记录当前的深度，并记录当前值。

class Solution {
          
   
    int maxDeep = -1;
    int ans;

    public int findBottomLeftValue(TreeNode root) {
          
   
        midOrder(root, 0);
        return ans;
    }

    public void midOrder(TreeNode root, int deep) {
          
   
        if (root == null) return ;

        midOrder(root.left, deep + 1);
        
        // 判断深度是否加深
        if (deep > maxDeep) {
          
   
            maxDeep = deep;
            ans = root.val;
        }
        midOrder(root.right, deep + 1);
    }
}