LeetCode 513 找树左下角的值（带动画图解！)

1 题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3] 输出: 1 示例 2:

输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7

2 解题思路

题意理解：该题要求找到最底层，最左侧的节点，言下之意，底层优先级更高，我们可以先获取该树的最大深度（递归、迭代），获取最大深度后用层次遍历，遍历到最大层时，直接输出第一个访问的节点。

使用递归策略获取最大深度 终止条件：当访问节点为空，返回0。 参数返回值：参数为当前访问节点，返回值当前子树最大深度。 单层函数实现逻辑： 何为单层递归逻辑？即我们将一棵二叉树视为只包含三个节点的树，即根节点、左子树、右子树。 我们在函数逻辑中实现对左右子树的操作。 返回左右子树深度最大值，然后将该值加1。 3 代码实现 import org.omg.CORBA.MARSHAL; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; /** * @author zdh * @date 2021/7/23 16:31 */ public class ButtonLeftVal { public int getDepth(TreeNode root) { if (root == null) { return 0;//终止条件，当节点为空，表示该树最大深度为0 } return Math.max(getDepth(root.left), getDepth(root.right)) + 1;//节点不为空，返回左右子树深度最大值，然后将该值加1。 } public int findBottomLeftValue(TreeNode root) { //使用层次遍历方法遍历树 int maxDepth = getDepth(root); Queue<TreeNode> queue = new LinkedList<>();//使用队列存储节点 Queue<Integer> depth = new LinkedList<>();//对应队列中每个节点的深度，二者入队出队顺序一致 queue.offer(root);//根节点入队 depth.offer(1);//根节点深度为1 TreeNode poll; int deep;//放在循环外面，减少空间消耗，降低空间复杂度 while (!queue.isEmpty()) { poll = queue.poll(); deep = depth.poll();//弹出队首元素 if (deep == maxDepth)//当当前处理节点的深度等于该树的最大深度时，第一个访问的节点就是我们要的值，直接返回。 return poll.val; if (poll.left != null) { //当前节点左子入队 queue.offer(poll.left); depth.offer(deep + 1); } if (poll.right != null) { //当前节点右子入队 queue.offer(poll.right); depth.offer(deep + 1); } } return 0;//否则返回0，只有root为空时会执行该语句。 } } 4 动画展示 递归部分