算法-树相关

树

树是一种非线性数据结构。树结构的基本单位是节点。节点之间的链接，称为分支（branch）。节点与分支形成树状，结构的开端，称为根（root），或根结点。根节点之外的节点，称为子节点（child）。没有链接到其他子节点的节点，称为叶节点（leaf）。

解题方法

一个中心

一个中心指的是树的遍历。有关于树的算法题核心都是树的遍历。

树的遍历有先后之分，如前中后序遍历，也有方向之分，比如广度优先，以及深度优先。

对于遍历形式，常用的是递归，当然也有利用栈进行迭代遍历（这是本质）

如94. 二叉树的中序遍历，递归代码如下：

var inorderTraversal = function (root) {  const res = []  const inorder = (root) => {    if (!root) {      return    }    // 前中后遍历调整res.push 的位置即可    inorder(root.left)    res.push(root.val)    inorder(root.right)  }  inorder(root)  return res}

其迭代写法如下：

var inorderTraversal = function (root) {  const res = []  const stack = []  while (root || stack.length) {    // 当栈空或者节点为空时，退出循环    while (root) {      // 一直往左子树的方向找，直至其左孩子为空跳出循环      stack.push(root)      root = root.left    }    // 将该节点取出，其左孩子已为空，此时读出根节点存入res，即自身    root = stack.pop()    res.push(root.val)    // 左根右，开始读右孩子    root = root.right  }  return res}

两个基本点

上面提到了树的遍历有两种基本方式，分别是深度优先遍历（以下简称 DFS）和广度优先遍历（以下简称 BFS），这就是两个基本点。这两种遍历方式下面又会细分几种方式。比如 DFS 细分为前中后序遍历， BFS 细分为带层的和不带层的。

DFS
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。简单概括为一直向下寻找，找不到就回上一个节点再基于此往另一个下方找。
BFS
BFS 也是图论中算法的一种，不同于 DFS， BFS 采用横向搜索的方式，在数据结构上通常采用队列结构。注意，DFS 我们借助的是栈来完成，而这里借助的是队列。
对于 BFS，需要强调一下层次遍历和 BFS 是完全不一样的东西。BFS 的核心在于求最短问题时候可以提前终止，这才是它的核心价值，层次遍历是一种不需要提前终止的 BFS 的副产物。这个提前终止不同于 DFS 的剪枝的提前终止，而是找到最近目标的提前终止。比如我要找距离最近的目标节点，BFS 找到目标节点就可以直接返回。而 DFS 要穷举所有可能才能找到最近的，这才是 BFS 的核心价值。
BFS 比较适合找最短距离/路径和某一个距离的目标。

三种题型

搜索类
搜索类只有两种解法，那就是 DFS 和 BFS，几乎所有的搜索类题目都可以方便地使用递归来实现。
例题：剑指 Offer 34. 二叉树中和为某一值的路径
其解题思路主要是暴力，将某个节点加入路径数组，然后再将其子节点递归，并更新 num 值，若遍历到叶子节点，判断是否符合条件，若符合条件则加入结果数组。
此题卡了半小时，错在两个地方，第一个是深浅拷贝的概念，需要简易地拷贝一份新的路径数组，否则后续路径数组的变更，都会影响到结果数组已经存好的路径。以及注意叶子节点需要及时弹出。
一开始还考虑了剪枝优化，但提交才发现有负数的存在，所以不能单纯的通过当前节点值与 num 的关系进行剪枝。

var pathSum = function (root, target) {  function dfs(result, pathRecord, cur, num) {    if (!cur) {      // 空节点返回      return    }    pathRecord.push(cur.val) // 选择该节点    if (!cur.left && !cur.right) {      // 找到了叶子节点      if (num == cur.val) {        result.push([...pathRecord]) // 简易深拷贝      }      pathRecord.pop() // 弹出叶子节点      return    }    // 深度遍历，递归，更新num值    dfs(result, pathRecord, cur.left, num - cur.val)    dfs(result, pathRecord, cur.right, num - cur.val)    pathRecord.pop() // 清除该节点  }  let res = [] // 结果数组，存储路径数组  let path = [] //路径数组，存储路径节点  dfs(res, path, root, target)  return res}

构建类
除了搜索类，另外一个大头是构建类。构建类又分为两种：普通二叉树的构建和二叉搜索树的构建。
修改类
修改类的题目也是要基于搜索算法的，只不过占比较少。

四个重要概念
1. 二叉搜索树
  二叉搜索树具有下列性质的二叉树：
  - 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  - 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  - 左、右子树也分别为二叉排序树；
  - 没有键值相等的节点。
  - 其中序遍历是有序的，可通过该方式验证是否为二叉搜索树。98. 验证二叉搜索树
代码如下:
```
var isValidBST = function (root) {  let pre = -Infinity  let inorder = (root) => {    if (!root) {      return true    }    if (!inorder(root.left)) {      // 该判断主要判断左子树是否符合平衡二叉树      return false    }    if (root.val <= pre) {      // 由于是中序遍历，故若当前的值比之前遍历的还要小，说明不是平衡二叉树。      return false    }    pre = root.val // 遍历完该点，需要及时更新参考值    return inorder(root.right) // 再去判断右子树是否符合条件，才可以对一个节点的递归判断下结论  }  return inorder(root)}
```
递归的时候需要注意挺多东西，因为左右子树也需要满足平衡二叉树，所以如果当前专注的节点左子树不是平衡二叉树时，可以直接 return false。若当前专注节点左子树无问题，那么更新参照值，并去判断右子树。
实际上，迭代写法更加简洁直观，并且和中序遍历迭代的写法非常像，仅仅多加了一个判断语句：
```
var isValidBST = function (root) {  let pre = -Infinity  const stack = []  while (stack.length || root) {    while (root) {      stack.push(root)      root = root.left    }    root = stack.pop()    if (root.val <= pre) {      return false    }    pre = root.val    root = root.right  }  return true}
```
21.10.08 更新：783. 二叉搜索树节点最小距离
思路同样是中序遍历，中间处理。
```
var minDiffInBST = function (root) {  // 递归写法  let pre = null  let min = Infinity  let dfs = (root) => {    if (!root) {      return    }    dfs(root.left)    if (pre) {      min = Math.min(min, root.val - pre.val)    }    pre = root    dfs(root.right)  }  dfs(root)  return min}
```
1. 完全二叉树
  一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
  如下图：
  
  根据完全二叉树的性质，我们可以轻松知道节点的父子关系，已知一个节点的编号是 i，那么其左子节点就是 2 i，右子节点就是 2 i + 1，父节点就是 (i + 1) / 2。
  根据该性质，我们可以把很多不是完全二叉树的二叉树设想为完全二叉树，方便解题。如：662. 二叉树最大宽度
2. 路径
  树的路径这种题目的变种很多，算是一种经典的考点了。
  例题：124. 二叉树中的最大路径和
3. 距离
  和路径类似，距离也是一个相似且频繁出现的一个考点，并且二者都是搜索类题目的考点。原因就在于最短路径就是距离，而树的最短路径就是边的数目。
七个技巧
1. dfs(root)
  形参命名最好也和顶层函数的命名一样，避免出错。
2. 单双递归
  单递归最常用，而双递归一般用在任意节点开始 xxxx 或者所有 xxx这样的题目中。
  如：面试题 04.12. 求和路径中便明确要求路径不一定非得从二叉树的根节点或叶节点开始或结束，再加上此题值可正可负，这就说明，我们需要对所有节点进行暴力统计。可以先写好从根节点出发的 dfs 递归函数，再在主函数中进行一次节点的递归即可。代码如下：
```
// 一开始按照路径和的形式去写，将路径加入数组，统计最后的长度，实在没必要，因为这题不需要你统计路径，一开始的做法产生的空间开销很大。var pathSum = function (root, sum) {  if (!root) {    return 0  }  return (    dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)  )}var dfs = (root, val) => {  if (!root) {    return 0  }  let rest = val - root.val  let count = rest == 0 ? 1 : 0  count += dfs(root.left, rest)  count += dfs(root.right, rest)  return count}
```
  另外：563. 二叉树的坡度
  2021.10.07 这题简单题做了我非常久，在这里我得反思一下，因为自己太爱套模板了导致入手总是出差错，或者和最后的正确写法差一个百八千里，😭，我好菜啊啊。
  双递归确实是没错，但是我从根节点出发的递归都没写好哎哎哎
  代码如下：
```
/** * @param {TreeNode} root * @return {number} */var findTilt = function (root) {  if (!root) {    return 0  }  return (    Math.abs(dfs(root.left) - dfs(root.right)) +    findTilt(root.left) +    findTilt(root.right)  )}var dfs = (root) => {  if (!root) {    return 0  }  return root.val + dfs(root.left) + dfs(root.right)}
```
  反思：做双递归的时候，先明白单纯的 dfs 需要处理什么，不要把盲目地把主逻辑也放进 dfs 函数中，此题的主逻辑加减法交给顶层主函数递归！
  上一题，由于确认路径的条数需要往下深入，那么主逻辑就放在 dfs 函数中去做加和。
  而这一题中，由于最后的结果都是从当前节点得到，所以主逻辑便写在负责遍历节点的主函数中。
3. 前后遍历
  前后各对应方法为：
  自顶向下就是在每个递归层级，首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点，一般是通过参数传到子树中。
  自底向上是另一种常见的递归方法，首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。
  **直白地说：**就是主要地处理逻辑放在哪就是什么遍历，如前述所说的中序遍历，就将节点的入栈放在两个递归之间。同理，若是后序遍历，就将其放于两个递归之后。
4. 虚拟节点
  当你需要对树的头节点（在树中我们称之为根节点）进行修改的时候，就可以考虑使用虚拟指针的技巧了。
  另外一种是题目需要返回树中间的某个节点（不是返回根节点）。实际上也可借助虚拟节点。由于我上面提到的指针的操作，实际上，你可以新建一个虚拟头，然后让虚拟头在恰当的时候（刚好指向需要返回的节点）断开连接，这样我们就可以返回虚拟头的 next 就 ok 了。
  例题：814. 二叉树剪枝
  由于原有的头可能会被删去，即头也可能是 0 的情况，所以设置虚拟头方便操作。注意传入 dfs 的节点为虚拟节点，而虚拟节点设置的值可以任意（一般设为 -1 便于区分），因为虚拟节点绝对不会被 dfs 处理（dfs 函数返回的是子树的节点和，而第一层递归中，是对虚拟节点的左右节点进行加和，故与虚拟节点的取值无关）
  其代码如下：属于后序收集，以一种大局观的方式来看，dfs 的作用，就是计算当前节点（包括当前节点）下所有的子节点之和。统计完之后，进入 if 条件判断，若子树和为 0，将其剪去。
```
var pruneTree = function (root) {  let fakeNode = new TreeNode(-1, root)  let dfs = (root) => {    if (!root) {      return 0    }    let left = dfs(root.left)    let right = dfs(root.right)    if (left == 0) {      root.left = null    }    if (right == 0) {      root.right = null    }    return root.val + left + right  }  dfs(fakeNode)  return fakeNode.left}
```
  例题 2：1325. 删除给定值的叶子节点
  思路是后序遍历，自底向上，找到当前节点的左右节点（或子树），若当前节点为叶子节点，且满足题意，则删除，删除需要通过父节点的指针，故需要记录父节点的位置。
```
var removeLeafNodes = function (root, target) {  let dfs = (root, parent, leftChild = true) => {    if (!root) {      return    }    dfs(root.left, root, true)    dfs(root.right, root, false)    if (root.val == target && parent && !root.left && !root.right) {      if (leftChild) {        parent.left = null      } else {        parent.right = null      }    }  }  // 由于需要删除叶子节点，故需要记录当前节点的父节点是谁  let fakeNode = new TreeNode(-1, root)  dfs(root, fakeNode)  return fakeNode.left}
```
  而在题解中，我看到一个更简洁直观的做法：
  其思路同理，也是后序遍历，自底向上。即先处理完叶子节点，再处理相对应的根节点（不是最顶那个节点，相对来说，二叉树的递归题目都可以简化成三角形结构）
```
var removeLeafNodes = function (root, target) {  if (!root) {    return null  }  root.left = removeLeafNodes(root.left, target)  root.right = removeLeafNodes(root.right, target)  // 后序逻辑写在这  if (root.val == target && !root.right && !root.left) {    return null  }  return root}
```
5. 边界
  边界主要用于确定返回时机，通常有空节点与叶子节点返回，前者直接判断，后者则判断是否存在左右子树。
6. 参数扩展大法
  即每层递归都传入一些上一层的信息，但比较巧用的还是传递结果值，在递归的时候，维护这个结果。如最大最小之类的结果，可以在递归的过程中做更新。
  例题：783. 二叉搜索树节点最小距离
  此题单纯的利用二叉搜索树的性质：中序遍历递增，也可以做，思路便是和参数扩展相似，也是在中序遍历递归的过程中维护这个最小值。
  从性质出发：答案从相邻的节点中求得。那也可以换一种思路，采用后序遍历（左右根），递归地将每个节点都与其左右孩子节点做差，维护更新一个最小值。
  细节上，下一层递归时，要将根节点的值传入，右孩子减根，根减左孩子，这样子才能得到正值。
  @Todo：2021.10.09 哎呀我是真的看不懂，递归图也画了
  代码如下：
```
var minDiffInBST = function (root) {  // 递归写法  let dfs = (root, lower, upper) => {    if (!root) {      return upper - lower    }    let left = dfs(root.left, lower, root.val)    let right = dfs(root.right, root.val, upper)    return Math.min(left, right)  }  return dfs(root, -Infinity, Infinity)}
```
7. 返回数组
  例题：865. 具有所有最深节点的最小子树
  不仅需要记录深度，还需要记录返回结果的节点。
```
var subtreeWithAllDeepest = function (root) {  let dfs = (root, depth) => {    if (!root) {      return [root, depth]    }    let [leftNode, left_depth] = dfs(root.left, depth + 1)    let [rightNode, right_depth] = dfs(root.right, depth + 1)    if (left_depth == right_depth) return [root, left_depth]    if (left_depth > right_depth) return [leftNode, left_depth]    return [rightNode, right_depth]  }  return dfs(root, -1)[0]}
```

TAT，递归真的不够脑，明天下一章了，太难受了。

习题练习

21.10.5

102. 二叉树的层序遍历

层序遍历的核心便是利用队列。其思路时是，维护一个队列，首先让根节点先进入，并开始循环，条件为队列非空。进入循环后，需要将当前队列清空（即取出这一层所有的节点），并将其存入 res 中，同时，若该节点还有子节点，便再次加入到队尾。

var levelOrder = function (root) {  const res = []  if (!root) {    return res  }  const q = []  q.push(root)  while (q.length) {    const currentLen = q.length    res.push([])    for (let i = 0; i < currentLen; ++i) {      const node = q.shift()      res[res.length - 1].push(node.val)      if (node.left) q.push(node.left)      if (node.right) q.push(node.right)    }  }  return res}

通过层次遍历，可以轻松算出二叉树的深度，代码基本无异：104. 二叉树的最大深度

var maxDepth = function (root) {  let maxNum = 0  const res = []  if (!root) {    return res  }  const q = []  q.push(root)  while (q.length) {    const currentLen = q.length    res.push([])    for (let i = 0; i < currentLen; ++i) {      const node = q.shift()      res[res.length - 1].push(node.val)      if (node.left) q.push(node.left)      if (node.right) q.push(node.right)    }    maxNum++  }  return maxNum}// 递归写法// var maxDepth = function (root) {//     var dfs = (root) => {//         if (!root) return 0//         return Math.max(dfs(root.left), dfs(root.right)) + 1//     }//     return dfs(root)// };

cd ..