接着上一篇的二叉树相关题目，本节继续列举有关二叉树的题目。

首先是巩固之前学到的，本章节的重点是学习二叉树中的回溯思想。

还是结论先行👇

总结

• 二叉树的回溯多与路径相关。
• 二叉树中回溯的使用场景是：我们依赖一个变量，该变量存储的是当前节点的某个信息，而且该变量还是递归的入参，此时我们为了保证他在递归返回时值不发生变化，因此需要回溯递归前的操作。。
  • 确定递归需不需要入参时，往往考虑的是：该入参需要作为判断终止条件的辅助数据或需要在终止条件中使用
  • 一旦该入参代表的含义为当前节点的某些信息时，往往需要回溯，因此可以总结为：入参+递归+回溯往往同时出现
• 回溯的形象描述：将二叉树想象成一条树状的有积雪的马路，每当遇到一个分岔口时（二叉树的每个节点都可能是分岔口），我们先选择一条路前进（左子树/右子树），走到尽头时（叶子节点或遇到其他终止条件），我们要回到之前的分岔口（return）然后向另一条路探索，在回去的路上清理留下的脚步（回溯）。
• 当我们规定了当前的参数的含义，在整个递归过程中一定要保证其含义不变（循环不变量）。

复习--LeetCode-100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

这里与对称二叉树十分类似，都是需要两个节点指针进行比较。 我们可以使用层序遍历来解决，但是这里主要给出递归的思考与实现。

递归

递归分析:

• 返回值和入参：返回当前两个子节点所代表的子树是否相同，入参为左子树根和右子树根
• 终止条件：
  • 当两个节点都为空 true
  • 两个节点有一个节点不为空 false
  • 两个节点值不相同 false
• 单层递归逻辑：此时两个节点都存在并且值相同
  • 递归p树的左子树和q树的左子树是否相同
  • 递归p树的右子树和q树的右子树是否相同
  • 返回当前节点所代表树是否相同，由于此时当前节点已经相同，因此只需要其子树是否也相同的信息即可

实现：

function compareRecursive(leftNode, rightNode) {
  if (!leftNode && !rightNode) return true;
  if (!leftNode || !rightNode) return false;
  if (leftNode.val !== rightNode.val) return false;

  //左
  const isSameLeft = compareRecursive(leftNode.left, rightNode.left);
  //右
  const isSameRight = compareRecursive(leftNode.right, rightNode.right);
  //中
  const isSame = isSameLeft && isSameRight;
  return isSame;
}
var isSameTree = function (p, q) {
  return compareRecursive(p, q);
};

在上述递归分析中，你可能会想只要我判断出一个false就可以直接返回了，没错，这里可以利用我们之前所学习的中断递归的方法：判断+return；

我们并没有分析使用什么遍历方式，希望你能自己分析出来，由于我们每次递归判断的是当前节点所代表子树是否相同，因此需要子树的信息，那么后序显而易见。

回溯

LeetCode-257.二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

如下示例：输出["1->2->5","1->3"]

这道题不简单，利用到了回溯的思想，先不总结回溯，我们先按照之前所学求解本题。

首先明确使用什么方法遍历二叉树？

这里我们确定一条路径一定是遇到了叶子节点，此外，我们还需要收集到达该叶子节点所经过的所有节点。针对这个想法，我想前序遍历可能更加合适，只需要判断当前是否是叶子节点，如果是叶子节点就将所收集的路径节点format为一条路径，然后去寻找下一个叶子节点。

但是会遇到问题，我们找到了第一条路径后，当前收集的路径节点需要更新，我们怎么更新？

• 想法一：清空所有路径节点。如果这样做，你下一次遇到某个叶子节点时，此时路径集合中保留的路径是不完整的。
• 想法二：只清空当前叶子节点。如果这样，你再遍历到一条具有新的路径的叶子节点时，会保留之前的路径而使结果错误。

递归+回溯

以上两种想法都无法实现，现在一个可行的办法应该是：在递归遍历中：如果当前节点不是叶子节点，那么应该继续向其左子树和右子树递归遍历，假设此时遍历的是左子树，先将当前节点加入路径节点集合，然后进行递归，每次递归结束说明已经找到了一条路径，当递归返回时，我们再将之前的这个节点弹出节点集合就能实现了。

这就是回溯的思想，可能文字晦涩难懂，看看下面这张图再理解一下：

• 这里粉色箭头表示向左右孩子进行递归，绿色箭头表示回溯，path为经过的结点集合
• 实际上这里已经不是前序遍历了，例如节点1，我们在递归其左子树前需要将当前节点加入集合，然后当回溯回来后，我们还要递归其右子树，递归前又需要将当前节点加入集合。

结合代码再来理解一下：

function getPathsRecursive(node, pathNodes, path) {
  //----终止条件
  if (!node) return;
  //是叶子节点
  if (!node.left && !node.right) {
    //收集路径
    let curPath = "";
    for (let pathNode of pathNodes) {
      curPath += pathNode.val + "->"
    }
    curPath += node.val;
    path.push(curPath);
  }

  //----单层递归逻辑
  if (node.left) {
    pathNodes.push(node);
    getPathsRecursive(node.left, pathNodes, path);
    //回溯
    pathNodes.pop();
  }
  if (node.right) {
    pathNodes.push(node);
    getPathsRecursive(node.right, pathNodes, path);
    //回溯
    pathNodes.pop();
  }
}
var binaryTreePaths = function (root) {
  const path = [];
  getPathsRecursive(root, [], path);
  return path;
};

现在应该会有点感觉了吧，二叉树的回溯往往与路径相关，本题就是如此，我们需要获得每条路径，而每当遇到一个分岔口时（二叉树的每个节点都可能是分岔口），我们先选择一条路前进（左子树/右子树），走到尽头时（叶子节点或遇到其他终止条件），我们要回到之前的分岔口（return）向另一条路探索，在回去的路上清理留下的脚步（回溯）。

LeetCode-513.找树左下角的值

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

这里说的是最底层且最左边的，那么容易想到利用层序遍历，最后一层时返回队列第一个节点就是最底层最左边的节点了。

使用递归如何寻找最底层？利用节点的深度进行判断，深度最大的叶子节点就是最底层的节点，而至于最左边，无论我们采用什么序遍历，都是先左后右，因此只要当遇到了这个深度最大的叶子节点时就可以直接返回了。

问题来到了求深度最大的叶子节点，这道题不像之前求二叉树的最大深度了，因为当时我们使用的是后序遍历求根节点的高度，此时求最大深度的叶子节点应该如何做？ 分析递归：

• 外层变量：maxDepth 存储当前遍历的所有节点中，叶子节点的最大的深度；res 存储最大深度叶子节点的值
• 返回值和入参：无返回值（不需要像后序一样借助左右子树的信息，结果在外层变量中），由于需要判断当前叶子节点深度和当前最大深度的大小关系，因此需要入参深度 depth: 代表当前节点深度；
• 终止条件：
  • 如果是叶子节点，与最大深度比较，更新maxDepth; res; 返回当前深度
• 单层循环逻辑：
  • 每递归向下一个节点都将深度+1
  • 一定是先左后右，保证遇到最底层叶子节点时，触发终止条件的是最左边的节点

如上分析对应的代码如下：

并不能AC，因为我们的深度一直在增加，我们遇到了第一个叶子节点后更新了答案，然后继续向下寻找叶子节点时，depth并没有重置为当前节点的深度。

恍然大悟了嘛，此时我们再继续寻找的时候应该回溯depth;

递归 + 回溯

那么，

• 单层循环逻辑变为：
  • 每递归向下一个节点都将深度+1
  • 一定是先左后右，保证遇到最底层叶子节点时，触发终止条件的是最左边的节点
  • 递归返回时，深度-1，即保证当前节点的深度depth不变；（有点循环不变量的味道了）

实现：

var findBottomLeftValue = function (root) {
  let maxDepth = -Infinity;
  let res = root.val;
  function recusiveDepth(node, depth) {
    //----终止条件
    if (!node.left && !node.right) {
      if (depth > maxDepth) {
        maxDepth = depth;
        res = node.val;
      }
      return;
    }

    //单层循环逻辑
    if (node.left) {
      depth += 1
      recusiveDepth(node.left, depth);
      //回溯
      depth -= 1;
    }
    if (node.right) {
      depth += 1
      recusiveDepth(node.right, depth);
      //回溯
      depth -= 1;
    }
  }
  recusiveDepth(root, 1);
  return res;
};

再来总结一下回溯：回溯使用在我们依赖一个变量，该变量存储的是当前节点的某个信息，而且该变量还是递归的入参（终止条件需要该入参辅助），此时我们为了保证他在递归返回时值不发生变化，因此需要回溯递归前的操作；

LeetCode-112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false。

分析：

• 我们的目标是找到一条和为targetSum的路径，有关路径，
• 每到一个节点时，记录当前经过的节点总和是必要的，并且会作为终止条件在下一次递归时判断，因此要作为参数

都跟我们之前总结的相关，显而易见的回溯

递归+回溯

递归分析：

• 返回值和入参：
  • 返回当前路径和是否等于目标值
  • 入参：node当前节点； curSum 到达当前节点的路径总和
• 终止条件：
  • 当前节点为叶子节点，且路径总和为目标值时 true
• 单层递归逻辑：
  • 如果存在左子节点，将curSum+左子节点值 传入下次递归
  • 我们一旦找到了一条符合的路径，此时应该将结果返回出去，因此需要中断递归
  • 递归返回后回溯curSum
  • 右子节点同理

实现：

function hasPathSumRecursive(node, curSum, targetSum) {
  //----终止条件
  //叶子节点且当前值等于目标值
  if (!node.left && !node.right && curSum === targetSum) return true;

  //----单层递归逻辑
  if (node.left) {
    curSum += node.left.val;
    const res = hasPathSumRecursive(node.left, curSum, targetSum);
    //中断递归
    if (res) return res;
    //回溯
    curSum -= node.left.val;
  }

  if (node.right) {
    curSum += node.right.val;
    const res = hasPathSumRecursive(node.right, curSum, targetSum);
    //中断
    if (res) return res;
    //回溯
    curSum -= node.right.val;
  }
  return false;
}
var hasPathSum = function (root, targetSum) {
  if (!root) return false;
  //注意curSum的定义
  return hasPathSumRecursive(root, root.val, targetSum);
};

从本题中可以总结出：当我们规定了当前的参数的含义时，那么在整个递归过程中一定要保证其含义（循环不变量），如：本题中我们回溯的目标为curSum，他表示的是到达当前节点且包括当前节点所经过路径的总和，那么我们在一开始调用时，传入的就是root.val，并且在进入下一个递归前，我们加的是左/右子节点的值（因为我们要递归左/右子节点了，因此传入时要保证在递归的时候这个值的正确性）；