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

大家好，我是「柒八九」。

今天，我们继续探索JS算法相关的知识点。我们来谈谈关于树Tree 的相关知识点和具体的算法。

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

文章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; // 右侧子节点引用
 }
} 

- 中序遍历和后序遍历： 
    - 顺着指向左子节点的指针移动时，只将节点放入栈中，并不遍历遇到的节点
    - **「只有当到达最左子节点之后再从栈中取出节点遍历」**

    - 后序还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为**「当前节点的右子节点」**来决定此时是否可以遍历当前节点

二叉树相关算法

二叉树剪枝

题目描述：

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

❞

分析

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的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和 示例：输入: root = 4,9,0,5,1 输出: 1026
解释：

• 从根到叶子节点路径 4->9->5 代表数字 495
• 从根到叶子节点路径 4->9->1 代表数字 491
• 从根到叶子节点路径 4->0 代表数字 40
  因此，数字总和 = 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的路径的数目。
路径的定义为二叉树中「顺着指向子节点的指针向下移动所经过的节点」，但不一定从根节点开始，也不一定到叶节点结束。 输入：root = 10,5,-3,3,2,null,11,3,-2,null,1, sum = 8
输出：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()的时候，是不是感觉到虎躯一震。有一种似曾相识的感觉。

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

也是通过Sj-Si-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;
}

展开二叉搜索树

题目描述：

❝ 给定一棵二叉搜索树，调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。 输入：root = 5,1,7
输出：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的下一个节点。假设二叉搜索树中的节点的值都是唯一的， 输入：root = 2,1,3, p = 1
输出：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的两个节点。 输入: root = 8,6,10,5,7,9,11, k = 12
输出: 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版

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