问题

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

示例 1:
输入:

  1. 2<br />   / \<br />  1   3<br />输出：1<br /> <br />示例 2:<br />输入:<br />        1<br />       / \<br />      2   3<br />     /   / \<br />    4   5   6<br />       /<br />      7<br />输出：7

解法一：递归

这道题目用递归的话就就一直向左遍历，最后一个就是答案么？

肯定不是，一直向左遍历到最后一个，它未必是最后一行

我们来分析一下题目：在树的最后一行找到最左边的值
首先要是最后一行，然后是最左边的值

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行

所以要找深度最大的叶子节点

那么如何找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值

递归三部曲：

  • 确定递归函数的参数和返回值
    • 参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。这里就不需要返回值了，所以递归函数的返回类型为void

本题还需要类里的两个全局变量，maxLen用来记录最大深度，maxleftValue记录最大深度最左节点的数值

int maxLen = INT_MIN;   // 全局变量 记录最大深度
int maxleftValue;       // 全局变量 最大深度最左节点的数值
void traversal(TreeNode root, int leftLen)

那么递归函数的返回值为啥不能返回最长深度呢？ 递归函数什么时候要有返回值，什么时候不能有返回值？
如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！


本题我们是要遍历整个树找到最深的叶子节点，需要遍历整颗树，所以递归函数没有返回值

  • 确定终止条件

    • 当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度
      if (root.left == null && root.right == null) {
if (leftLen > maxLen) {
   maxLen = leftLen;           // 更新最大深度
   maxleftValue = root.val;   // 最大深度最左面的数值 
}
return;
}

  • 确定单层递归的逻辑

    • 在找最大深度的时候，递归的过程中依然要使用回溯
                     // 中
if (root.left) {   // 左
leftLen++; // 深度加一     
traversal(root.left, leftLen);
leftLen--; // 回溯，深度减一
}
if (root.right) { // 右
leftLen++; // 深度加一
traversal(root.right, leftLen);
leftLen--; // 回溯，深度减一
}
return;

      class Solution {
int maxLen = -1;
int maxleftValue;
void traversal(TreeNode root, int leftLen) {
   if (root.left == null && root.right == null) {
       if (leftLen > maxLen) {
           maxLen = leftLen;
           maxleftValue = root.val;
       }
       return;
   }
   if (root.left != null) {
       leftLen++;
       traversal(root.left, leftLen);
       leftLen--; // 回溯
   }
   if (root.right != null) {
       leftLen++;
       traversal(root.right, leftLen);
       leftLen--; // 回溯 
   }
   return;
}
int findBottomLeftValue(TreeNode root) {
   traversal(root, 0);
   return maxleftValue;
}
}

      //简化
class Solution {
int maxLen = -1;
int maxleftValue;
void traversal(TreeNode root, int leftLen) {
   if (root.left == null && root.right == null) {
       if (leftLen > maxLen) {
           maxLen = leftLen;
           maxleftValue = root.val;
       }
       return;
   }
   if (root.left != null) {
       traversal(root.left, leftLen + 1); // 隐藏着回溯
   }
   if (root.right != null) {
       traversal(root.right, leftLen + 1); // 隐藏着回溯
   }
   return;
}
int findBottomLeftValue(TreeNode root) {
   traversal(root, 0);
   return maxleftValue;
}
};

解法二：迭代法

class Solution {
    int findBottomLeftValue(TreeNode root) {
        int result = 0;
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    result = node.val;
                } // 记录最后一行第一个元素
                if (node.left != null) 
                    queue.offer(node.left);
                if (node.right != null) 
                    queue.offer(node.right);
            }
        }
        return result;
    }
}