我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第2篇文章，[点击查看活动详情]

杠杆的本质，是一种以小博大的模型

大家好，我是柒八九。

今天，我们继续探索JS算法相关的知识点。我们来谈谈关于<span style="font-weight:800;color:#FFA500;font-size:18px">{树|Tree }</span>的相关知识点和具体的算法。

如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。

文章list

1. 整数
2. 常规排序算法
3. 数组
4. 字符串
5. 链表
6. 栈
7. 队列

好了，天不早了，干点正事哇。

你能所学到的知识点

1. 知识点简讲
   • 树在前端开发中的应用场景
   • 二叉树深度优先遍历 递归和迭代的JS版本
2. 二叉树相关算法
3. 二叉搜索树（BST）相关算法

知识点简讲

树的简介

栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。

树在计算机领域中也有着广泛的应用，例如

• 在编译程序中，用树来表示源程序的语法结构

  • 在babel进行代码编译的时候，在中间过程(Trasnfrom)中就会生成代表源码代码的AST
  • 在前端框架(Vue/React)中，用element树来表示即将被渲染到页面的数据信息
  • 在React最新的Fiber框架中，还拥有一棵Fiber树，用于保存针对页面的副作用。

• 在数据库系统中，可用树来组织信息；

• 在分析算法的行为时，可用树来描述其执行过程等等。

树（Tree）是n（n>=0）个结点的有限集。

在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的结点；

• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3,...Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。

  二叉树和二叉搜索树

  二叉树中的节点最多只能有两个子节点：

• 一个是左侧子节点，
• 另一个是右侧子节点

且，二叉树是一种典型的具有递归性质的数据结构。

二叉搜索树（BST）是特殊的二叉树

• 只允许你在左侧节点存储（比父节点）小的值
• 在右侧节点存储（比父节点）大的值

  二叉树的数据结构

  用Node 类来表示二叉树中的每个节点，代码如下。

class Node {
 constructor(key) {
 this.key = key; // {1} 节点值
 this.left = null; // 左侧子节点引用
 this.right = null; // 右侧子节点引用
 }
} 

二叉树的遍历

针对二叉树的遍历，可以分为两大类。

1. <span style="font-weight:800;color:#FFA500;font-size:18px">{广度优先遍历|Breath-First-Search}</span> - BFS
   • 我们在队列中有过相关介绍，这里就不在赘述了。
2. <span style="font-weight:800;color:#FFA500;font-size:18px">{深度优先遍历|Depth-First-Search}</span> - DFS
   <br>而DFS又根据遍历根节点的先后顺序，分为
   1. <span style="font-weight:800;color:#FFA500;font-size:18px">{中序遍历|Inorder Traversal}</span>
   • 遍历左子树–>访问根–>遍历右子树;
   2. <span style="font-weight:800;color:#FFA500;font-size:18px">{前序遍历|Preorder Traversal}</span>
   • 访问根–>遍历左子树–>遍历右子树;
   3. <span style="font-weight:800;color:#FFA500;font-size:18px">{后序遍历|Postorder Traversal}</span>
   • 遍历左子树–>遍历右子树–>访问根;

下面我们来依次用代码实现各个遍历方式。

<span style="font-weight:800;color:#FFA500;font-size:18px">{中序遍历|Inorder Traversal}</span>

递归版本

function inOrderTraverse(root) {
 if (root == null) return; // 基线条件
 inOrderTraverse(root.left);
 console.log(root.data + " ");
 inOrderTraverse(root.right);
}

迭代版本

把递归代码改成迭代方式的代码通常需要用到栈。

• 二叉树的遍历总是从根节点开始的，但当第一次到达根节点时，并不是马上遍历根节点，而是顺着指向左子节点的指针向下直到叶子节点，也就是找到第一个真正被遍历的节点。
• 为了在一个节点被遍历之后能够接着回去遍历它的父节点
  • 可以在顺着指向左子节点的指针遍历二叉树时，把遇到的每个节点都添加到一个栈中
  • 当一个节点被遍历之后，就可以从栈中得到它的父节点

    
    function inOrderTraverse(root) {
    let result = [];
    let stack = new Stack(); // 这里的Stack()在前面的文章中有介绍
    let cur = root;
    while(cur || !stack.isEmpty()) { 
     while(cur){
     stack.push(cur);
     cur = cur.left;
     }
     cur = stack.pop();
     result.push(cur.val); // 操作当前节点
     cur = cur.right; 
    }
    return result;
    }

代码解释
- `cur`表示当前遍历的节点。
 - 如果该节点有左子节点，按照中序的遍历顺序，应该先遍历它的左子树。
 - 指向左子节点的指针一直向下移动，并**将沿途遇到的每个节点都添加到栈中**
 - `while(cur){ stack.push(cur); cur = cur.left; }`
- 第二个`while`结束之后，**最左子节点位于栈顶**
---
### <span style="font-weight:800;color:#FFA500;font-size:18px">{前序遍历|Preorder Traversal}</span>
#### 递归版本
```javascript
// 先序遍历
function preOrderTraverse(root) {
 if (root == null) return; // 基线条件
 console.log(root.data + " ");
 preOrderTraverse(root.left);
 preOrderTraverse(root.right);
}

迭代版本

前序遍历的迭代代码和中序遍历的迭代代码很类似。它们之间唯一的区别是在顺着指向左子节点的指针向下移动时，前序遍历将遍历遇到的每个节点并将它添加在栈中。

function preOrderTraverse(root) {
 let result = [];
 let stack = new Stack(); // 这里的Stack()在前面的文章中有介绍
 let cur = root
 while(cur || !stack.isEmpty()) { 
 while(cur){
 result.push(cur.val); // 操作当前节点
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.pop();
 cur = cur.right;
 }
 return result;
}

这里再多说一句，我们把中序遍历和前序遍历的迭代版本放一起，就会发现很像。

function xxOrderTraverse(root) {
 let result = [];
 let stack=new Stack(); 
 let cur = root
 while(cur || !stack.isEmpty() ) { 
 while(cur){
+ result.push(cur.val); // 中序遍历
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.pop();
+ result.push(cur.val); // 前序遍历
 cur = cur.right;
 }
 return result;
}

<span style="font-weight:800;color:#FFA500;font-size:18px">{后序遍历|Postorder Traversal}</span>

递归版本

 function postOrderTraverse(root) {
 if (root == null) return; // 基线条件
 postOrderTraverse(root.left);
 postOrderTraverse(root.right);
 console.log(root.data + " ");
}

迭代版本

当到达某个节点时，

• 如果之前还没有遍历过它的右子树就的前往它的右子节点
• 如果之前已经遍历过它的右子树那么就可以遍历当前节点

要根据它的右子树此前有没有遍历过确定是否应该遍历当前的节点。

function postOrderTraverse(root) {
 let result = [];
 let stack = new Stack();
 let cur = root;
 let prev = null;// 记录前一次被访问的节点信息
 while(cur || !stack.isEmpty()) {
 while(cur){
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.peek();
 if(cur.right && cur.right != prev){
 // 一个节点存在右子树且未被遍历
 cur = cur.right;
 } else {
 stack.pop();
 result.push(cur.val);
 prev = cur;
 cur = null;
 } 
 }
 return result; 
}

代码解释：

• prev就是遍历过的前一个节点，它的初始值为null。
  • 在准备遍历下一个节点之前，就把它指向当前遍历的节点
  • prev = cur; cur = null;
• cur表示当前到达的节点。
  • 如果该节点有右子树并且右子节点不是前一个遍历的节点，则表示它有右子树并且右子树还没有遍历过
  • cur.right && cur.right != prev

小结

它们的递归代码都很简单，只需要调整代码的顺序就可以.

迭代代码也很类似

• 它们都需要一个栈
  • stack = new Stack()
• 基本结构也很相像
  • 都有两个while循环并且它们的条件都一样
  • 第一个while
    • while(cur || !stack.isEmpty())
    • 当前元素非空 或者 栈非空
  • 第二个while
    • while(cur)
    • 当前元素非空
• 遍历当前节点的时机
  • 前序遍历：
    • 一边顺着指向左子节点的指针移动一边遍历当前的节点
    • 
  • 中序遍历和后序遍历：
    • 顺着指向左子节点的指针移动时，只将节点放入栈中，并不遍历遇到的节点
    • 只有当到达最左子节点之后再从栈中取出节点遍历
    • 
    • 后序还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为当前节点的右子节点来决定此时是否可以遍历当前节点
    • 

二叉树相关算法

二叉树剪枝

题目描述：

一棵二叉树的所有节点的值由0/1节点组成，请剪除该二叉树中所有节点的值全都是0的子树<br>

分析

1. 什么样的节点可以被删除
   • 首先，这个节点的值为0
   • 其次，如果它有子树，那么它的子树的所有节点都可以被删除
2. 后序遍历适合处理这个问题
   • 用后序遍历的顺序遍历到某个节点，那么它的左右子树的节点一定已经遍历过了

     代码实现

function pruneTree(root){
 if(root == null) return root; // 基线条件
 root.left = pruneTree(root.left);
 root.right = pruneTree(root.right);
 if(root.left == null 
 && root.right == null 
 && root.val == 0){
 return null
 }
 return root;
}

代码解释

• 每当遍历到一个节点，就要确定它是否有左右子树，
  • 如果左右子树都是空，并且节点的值是0
  • 那么就可以删除这个节点
• 所谓删除一个节点，就是返回null给它的父节点

  • return null

    从根节点到叶节点的路径数字之和

题目描述：

一棵二叉树中所有的节点都在0~9的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和
<br><br>示例：输入: root = [4,9,0,5,1]
输出: 1026<br>
解释：

• 从根到叶子节点路径 4->9->5 代表数字 495
• 从根到叶子节点路径 4->9->1 代表数字 491
• 从根到叶子节点路径 4->0 代表数字 40<br>
  因此，数字总和 = 495 + 491 + 40 = 1026
  

分析

1. 顺着指向子节点的指针路径向下遍历二叉树，每到达一个节点，相当于在路径表示的数字末尾添加一位数字
   • 最开始到达根节点4，然后到达节点9,此时路径表示的数字49 = 4x10 + 9
   • 然后向下到达节点5,此时路径表示的数字495 (49 x10 + 5)
2. 每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。
   • 如果这个节点还有子节点，就把值传下去继续遍历子节点
   • 先计算当前节点，再计算子节点 --> 前序遍历

     代码实现

function sumNumbers(root){
 return (function dfs(root,path){
 if(root == null) return 0; // 基线条件
 path = path * 10 + root.val;
 // 如果是叶子节点，返回对应的值
 if(root.left ==null && root.right == null){
 return path;
 }
 // 有子节点，把值path向下传递
 return dfs(root.left,path) + dfs(root.right,path)
 })(root,0)
}

代码解释

• 路径定义是从根节点开始到叶节点结束，因此只有遇到叶节点才返回路径表示的数字
  • if(root.left) ==null && root.right ==null) return path
• 在遇到叶节点之前就结束的路径，应该返回0
  • 如果在某个非叶子节点，不存在左子树，那当遍历左子树时，此时值为null,如果从中获取节点的值xx.val就会报错。所以针对这种情况需要做一个容错处理

  • if(root == null) return 0;

    向下的路径节点值之和

题目描述：

给定一棵二叉树和一个值sum,求二叉树中节点值之和等于sum的路径的数目。
<br>路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束。
<br><br>输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
<br>输出：3

分析

1. 路径的起止节点的不确定性给计算路径经过的节点值之和带来了很大的难度
   • 虽然路径不一定从根节点开始，但仍然可以求得从根节点开始到达当前遍历节点的路径所经过的节点值之和。
2. 在路径上移动时把所有累加的节点值之和都保存下来，就容易知道是否存在从任意节点出发的值为给定sum的路径
3. 当遍历到一个节点时，先累加从根节点开始的路径上的节点值之和，再计算到它的左右子节点的路径的节点值之和。
   • 采用前序遍历

     代码实现

function pathSum(root,sum){
 let sumToCount = new Map();
 sumToCount.set(0,1);
 return (function dfs(root,sum,sumToCount,path){
 if(root ==null) return 0;
 path+=root.val;
 let count = sumToCount.get(path -sum) || 0;
 sumToCount.set(path,(sumToCount.get(path)||0)+1);
 count += dfs(root.left,sum,sumToCount,path);
 count += dfs(root.right,sum,sumToCount,path);
 sumToCount.set(path,sumToCount.get(path) -1);
 return count;
 })(root,sum,sumToCount,0)
}

代码解释

• path表示从根节点开始的路径已经累加的节点值之和，并保存到哈希表sumToCount
  • 初始值为sumToCount.set(0,1) ==> sum为0的个数为1个
• sumToCount的
  • 键是累加的节点值之和
  • 值是每个节点值之和出现的次数
• 当遍历到一个节点时，就把当前的节点值累加到path中
  • path += root.val
• 在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 path 减去 sum
  • 如果这个和之前出现过(sumToCount.get(path -sum)存在)，则将出现的次数+1
  • 如果不存在，count = 0
• 更新哈希表sumToCount.set(xx,xx)
  • 累加节点值之和path
  • path出现的次数
• 当递归函数dfs结束时，程序将回到节点的父节点，也就是说，在函数结束之前需要将当前节点从路径中删除，从根节点到当前节点累加的节点值之和也要从哈希表sumToCount中删除
  • sumToCount.set(path,sumToCount.get(path) -1);

举一反三

在看到xxtoXX = new Map()的时候，是不是感觉到虎躯一震。有一种似曾相识的感觉。

我们在数组的一章中介绍过累加数组数字求子数组之和 （S_i）,处理数组内容未整数的子树组相关问题。

也是通过S_j-S_i-1的数据关系，来计算子数组相关问题。而这个有一个比较关键的术语叫 --- 前缀和(我们后期会单独写一篇关于此类问题的文章)

二叉搜索树（BST）

二叉搜索树（BST）是特殊的二叉树，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。

二叉树的3种不同的深度优先搜索算法都使用于二叉搜索树，但中序遍历是解决二叉搜索树相关面试题最常用的思路，这是因为中序遍历按照节点值递增的顺序遍历二叉搜索树的每个节点。

如果二叉搜索树的高度为h,那么在二叉搜索树中根据节点值查找对应节点的时间复杂度是O(h)。

function searchBST(root,val){
 let cur = root;
 while(cur){
 if(cur.val == val){
 break;
 }
 if(cur.val < val){
 cur = cur.right;
 }else{
 cur = cur.left;
 }
 }
 return cur;
}

展开二叉搜索树

题目描述：

给定一棵二叉搜索树，调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。
<br><br>输入：root = [5,1,7]
<br>输出：[1,null,5,null,7]

分析

1. 需要按照节点的值递增的顺序遍历二叉搜索树中的每个节点，并将节点用指向右子节点的指针连接起来。
2. 采用中序遍历，只是在每遍历到一个节点要把前一个节点的指向右子节点的指针指向当前节点

   代码实现

function increasingBST(root){
 let stack = new Stack();
 let cur = root;
 let prev = null;
 let first = null;
 while(cur || !stack.isEmpty()){
 while(cur){
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.pop();
 if(prev){
 prev.right = cur;
 }else {
 first = cur;
 }
 prev = cur;
 cur.left = null;
 cur = cur.right;
 }
 return first;
}

代码解释

• 变量prev表示前一个遍历到的节点
• 当遍历到当前节点cur时，
  • 把变量prev的右子节点的指针指向cur
    • prev.right = cur
  • 并将cur指向左子节点的指针设为null
    • cur.left = null
• 展平之后的二叉搜索树的根节点是值最小的节点，也是中序遍历第一个被遍历到的节点。我们用first来保存这个信息
  • 当prev为null时first = cur

二叉搜索树的下一个节点

题目描述：

给定一棵二叉搜索树和它的一个节点p,请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中的节点的值都是唯一的，
<br><br>输入：root = [2,1,3], p = 1
<br>输出：2

时间复杂度O(n)的解法

分析

1. 采用二叉树的中序遍历
2. 用一个布尔值found来记录已经遍历到的节点p
   • 初始化为false
   • 遍历到节点p就将它设为true
   • 在这个变量变成true之后遍历到的第一个节点就是要找的节点

function inorderSuccessor(root,p){
 let stack = new Stack();
 let cur = root;
 let found = false;
 while(cur || !stack.isEmpty()){
 while(cur){
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.pop();
 if(found){
 break;
 }else if(cur == p){
 found = true;
 }
 cur = cur.right;
 }
 return cur;
}

时间复杂度O(h)的解法

1. 在中序遍历的情况下，下一个节点的值一定不小于节点p的值，而且还是大于或等于节点p的值的所有节点中最小的一个。
2. 从根节点开始，每到达一个节点就比较子树根节点的值和节点p的值。
   • 如果当前节点的值小于或者等于p的值，那么节点p的下一个节点应该在它的右子树
   • 如果当前节点的值大于节点p的值，那么当前节点有可能是它的下一个节点。
     • 此时当前节点的值比节点p的值大，但节点p的下一个节点是所有比它大的节点中值最小的一个
     • 接下来前往当前节点的左子树，确定是否能找到值更小但仍然大于节点p的值的节点
     • 重复这样的比较，直到找到最后一个大于节点p的值的节点，就是节点p的下一个节点

function inorderSuccessor(root,p){
 let cut = root;
 let result = null;
 while(cur){
 if(cur.val > p.val){
 result = cur;
 cur = cur.left;
 }else{
 cur = cur.right;
 }
 }
 return result;
}

• 变量result记录节点p的下一个节点。
  • 每当找到一个值大于p的节点，就更新变量result
    • result = cur
  • 并接着前往左子树看能否找到更小但仍然大于节点p的值的节点
    • cur = cur.left
• 由于while循环每次运行一次都会顺着指向左子节点或右子节点的指针向前下一层，因此while循环执行的次数等于二叉搜索树的深度

所有大于或等于节点的值之和

题目描述：

给定一棵二叉搜索树，请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。

分析

1. 该题与节点值的大小顺序相关，因为要找出比某节点的值大的所有节点。在二叉搜索树常规的遍历算法中，只有中序遍历是按照节点值递增的顺序遍历所有节点的。
2. 二叉搜索树的中序遍历按照节点的值从小到大按顺序遍历，也就是当遍历到某个节点时比该节点的值小的都已经遍历过。
   • 题目要求把每个节点的值替换成大于或等于该节点的值的所有节点的值之和
   • 常规的中序遍历行不通
3. 改变中序遍历的顺序，先遍历右子树，再遍历根节点，最后遍历左子树。

   代码实现

function converBST(root){
 let stack = new Stack();
 let cur = root;
 let sum = 0;
 while(cur || !stack.isEmpty()){
 while(cur){
 stack.push(cur);
 cur = cur.right;
 }
 cur = stack.pop();
 sum+=cur.val;
 cur.val = sum;
 cur = cur.left;
 }
 return root;
}

代码解释

• 在常规的中序遍历中，第二个while循环是顺着指向左子节点的指针向下移动的。
• 在此题中，是顺着指向右子节点的指针向下移动
  • cur = cur.right
• sum用来累加遍历过的节点的值。当遍历过一个节点时，值比它大的所有节点都已经遍历过了。
  • 因此，sum就是所有大于或等于当前节点的值之和

  • cur.val = sum

    二叉搜索树中两个节点的值之和

题目描述：

给定一棵二叉搜索树和一个值k，请判断该二叉搜索树中是否存在值之和等于k的两个节点。
<br><br>输入: root = [8,6,10,5,7,9,11], k = 12
<br>输出: true ==> 节点 5 和节点 7 之和等于 12

利用哈希表，空间复杂度O(n)的解法

1. 利用哈希表保存节点的值。而在JS中对象的底层实现就是HashMap
   • let map = {};
2. 每遍历到一个节点(节点的值记为v),就在哈希表中查看是否存在值为k-v的节点。
   • 如果存在，就表示存在值之和等于k的两个节点

function findTarget(root,k){
 let map = {};
 let stack = new Stack();
 let cur = root;
 while(cur || !stack.isEmpty()){
 while(cur){
 stack.push(cur);
 cur = cur.left;
 }
 cur = stack.pop();
 if(map[`${k - cur.val}`]){
 return true;
 }
 map[`${cur.val}`] = true;
 cur = cur.right
 }
 return false;
}

• 该算法使用任何二叉树

• 当然，我们也可以用Set()来替换对象，用于存储cur.val

  后记

  分享是一种态度。

参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版

全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。