513.找左下角的值
怎么找二叉树的左下角？ 递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值_哔哩哔哩_bilibili
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7提示:
- 二叉树的节点个数的范围是
[1,104]-231 <= Node.val <= 231 - 1
第一反应是找二叉树最深的路径，然后返回最深路径的最左边的节点。
如何找到最左边的节点呢？可以前序遍历，保证左边优先搜索，然后记录深度最大的叶子节点，此时就是树的最后一行的最左边的值。
递归三部曲：
1、确定递归函数的参数和返回值：
参数是传入的根节点，返回值是节点数，为int类型
class Solution{
public int findBottomLeftValue(TreeNode root){
}
}2、确定终止条件：
遇到叶子节点的时候，就需要统计一下最大深度，所以需要遇到叶子节点来更新最大深度
if(root == null) return;
if(root.left == null && root.right == null){
}3、确定单层递归的逻辑：
如果当前节点的左孩子不为空，则遍历到左孩子，深度加1；如果当前节点的右孩子不为空，则遍历到右孩子，深度加1
if (root.left != null) findLeftValue(root.left, deep + 1);
// 递归查找右子树的最左边节点，深度加 1
if (root.right != null) findLeftValue(root.right, deep + 1);综合代码：
// 递归法
class Solution {
// 记录当前最深层级
private int Deep = -1;
// 存储最底层最左边节点的值
private int value = 0;
// 公有方法，用来找到最底层最左边的节点的值
public int findBottomLeftValue(TreeNode root) {
// 将根节点的值赋给 value
value = root.val;
// 调用私有方法开始递归查找最左边的节点，并传入初始深度为 0
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;
}
}
// 递归查找左子树的最左边节点，深度加 1
if (root.left != null) findLeftValue(root.left, deep + 1);
// 递归查找右子树的最左边节点，深度加 1
if (root.right != null) findLeftValue(root.right, deep + 1);
}
}
112.路径总和
拿不准的遍历顺序，搞不清的回溯过程，我太难了！ | LeetCode：112. 路径总和_哔哩哔哩_bilibili
给你二叉树的根节点
root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：
- 树中节点的数目在范围
[0, 5000]内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
第一反应是遍历这棵二叉树，然后把一条路径的值相加，等于目标整数则返回true，不符合则返回false
递归三部曲：
1、确定参数和返回值。参数是根节点，返回值为boolean类型。
class Solution{
public boolean hasPathSum(TreeNode root, int targetSum){
if(root == null){
return false;
}
}
}2、确定终止条件：可以让计数器count 初始为目标值targetSum,遍历路径的过程中逐步相减，如果最后count = 0,同时遍历到了叶子节点，则return true；如果遍历到了叶子节点，count不为0，则return false
targetSum -= root.val;
// 如果当前节点是叶子节点
if (root.left == null && root.right == null) {
// 判断目标和是否为 0，若为 0 则返回 true，否则返回 false
return targetSum == 0;3、确定单层递归的逻辑：
if (root.left != null) {
// 递归调用 hasPathSum 函数，传入左子节点和更新后的目标和
boolean left = hasPathSum(root.left, targetSum);
// 如果左子树存在满足条件的路径，直接返回 true
if (left) { // 已经找到
return true;
}
}
// 如果当前节点有右子节点
if (root.right != null) {
// 递归调用 hasPathSum 函数，传入右子节点和更新后的目标和
boolean right = hasPathSum(root.right, targetSum);
// 如果右子树存在满足条件的路径，直接返回 true
if (right) { // 已经找到
return true;
}
}综合代码：
```java
class Solution {
// 判断是否存在从根节点到叶子节点的路径，使得路径上节点值之和等于目标和
public boolean hasPathSum(TreeNode root, int targetSum) {
// 如果根节点为空，直接返回 false
if (root == null) {
return false;
}
// 减去当前节点的值，更新目标和
targetSum -= root.val;
// 如果当前节点是叶子节点
if (root.left == null && root.right == null) {
// 判断目标和是否为 0，若为 0 则返回 true，否则返回 false
return targetSum == 0;
}
// 如果当前节点有左子节点
if (root.left != null) {
// 递归调用 hasPathSum 函数，传入左子节点和更新后的目标和
boolean left = hasPathSum(root.left, targetSum);
// 如果左子树存在满足条件的路径，直接返回 true
if (left) { // 已经找到
return true;
}
}
// 如果当前节点有右子节点
if (root.right != null) {
// 递归调用 hasPathSum 函数，传入右子节点和更新后的目标和
boolean right = hasPathSum(root.right, targetSum);
// 如果右子树存在满足条件的路径，直接返回 true
if (right) { // 已经找到
return true;
}
}
// 若左右子树均不存在满足条件的路径，返回 false
return false;
}
}
```