513. 找树左下角的值-day16

本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了反而用递归的话会比较难一点。我们依然还是先介绍递归法。咋眼一看这道题目用递归的话就就一直向左遍历最后一个就是答案呗没有这么简单一直向左遍历到最后一个它未必是最后一行啊。我们来分析一下题目在树的最后一行找到最左边的值。首先要是最后一行然后是最左边的值。如果使用递归法如何判断是最后一行呢其实就是深度最大的叶子节点一定是最后一行。如果对二叉树深度和高度还有点疑惑的话请看二叉树我平衡么。所以要找深度最大的叶子节点。那么如果找最左边的呢可以使用前序遍历这样才先优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。递归三部曲确定递归函数的参数和返回值参数必须有要遍历的树的根节点还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了所以递归函数的返回类型为void。本题还需要类里的两个全局变量maxLen用来记录最大深度maxleftValue记录最大深度最左节点的数值。有的同学可能疑惑为啥不能递归函数的返回值返回最长深度呢其实很多同学都对递归函数什么时候要有返回值什么时候不能有返回值很迷茫。如果需要遍历整颗树递归函数就不能有返回值。如果需要遍历某一条固定路线递归函数就一定要有返回值初学者可能对这个结论不太理解别急后面我会安排一道题目专门讲递归函数的返回值问题。这里大家暂时先了解一下。本题我们是要遍历整个树找到最深的叶子节点需要遍历整颗树所以递归函数没有返回值。确定终止条件当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。确定单层递归的逻辑在找最大深度的时候递归的过程中依然要使用回溯// 递归法 class Solution { private int Deep -1; private int value 0; public int findBottomLeftValue(TreeNode root) { value root.val; findLeftValue(root,0); return value; } private void findLeftValue (TreeNode root,int deep) { if (root null) return; if (root.left null root.right null) { if (deep Deep) { value root.val; Deep deep; } } if (root.left ! null) findLeftValue(root.left,deep 1); if (root.right ! null) findLeftValue(root.right,deep 1); } }//迭代法 class Solution { public int findBottomLeftValue(TreeNode root) { QueueTreeNode queue new LinkedList(); queue.offer(root); int res 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { TreeNode poll queue.poll(); if (i 0) { res poll.val; } if (poll.left ! null) { queue.offer(poll.left); } if (poll.right ! null) { queue.offer(poll.right); } } } return res; } }