❝ 杠杆的本质,是一种以小博大的模型 ❞
大家好,我是「柒八九」。
今天,我们继续探索JS算法相关的知识点。我们来谈谈关于树Tree 的相关知识点和具体的算法。
如果,想了解其他数据结构的算法介绍,可以参考我们已经发布的文章。如下是算法系列的往期文章。
好了,天不早了,干点正事哇。
❝
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; // 右侧子节点引用
}
}
针对二叉树的遍历,可以分为两大类。
BFS
DFS
而DFS
又根据「遍历根节点的先后顺序」,分为
1. 中序遍历Inorder Traversal
- 遍历左子树–>「访问根」–>遍历右子树;
1. 前序遍历Preorder Traversal
- 「访问根」–>遍历左子树–>遍历右子树;
1. 后序遍历Postorder Traversal
- 遍历左子树–>遍历右子树–>「访问根」;下面我们来依次用代码实现各个遍历方式。
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
结束之后,「最左子节点位于栈顶」// 先序遍历
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;
}
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
的子树
❞
0
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;
}
代码解释
null
给它的父节点 return null
题目描述:
❝ 一棵二叉树中所有的节点都在
0~9
的范围之内,从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和 示例:输入: root = 4,9,0,5,1 输出: 1026 解释:
❞
4
,然后到达节点9
,此时路径表示的数字49 = 4x10 + 9
5
,此时路径表示的数字495
(49 x10 + 5
)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
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
❞
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)
存在),则将出现的次数+1count = 0
sumToCount.set(xx,xx)
path
dfs
结束时,程序将回到节点的父节点,也就是说,在函数结束之前需要将当前节点从路径中删除,从根节点到当前节点累加的节点值之和也要从哈希表sumToCount
中删除 sumToCount.set(path,sumToCount.get(path) -1);
在看到xxtoXX = new Map()
的时候,是不是感觉到虎躯一震。有一种似曾相识的感觉。
我们在数组的一章中介绍过「累加数组数字求子数组之和 (Si)」,处理数组内容未「整数」的子树组相关问题。
也是通过Sj-Si-1的数据关系,来计算「子数组」相关问题。而这个有一个比较关键的术语叫 --- 「前缀和」(我们后期会单独写一篇关于此类问题的文章)
「二叉搜索树」(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
❞
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
❞
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;
}
p
的值,而且还是大于或等于节点p
的值的「所有节点中最小的一个」。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
**循环执行的次数等于二叉搜索树的深度」题目描述:
❝ 给定一棵二叉搜索树,请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。
❞
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 ❞
HashMap
let map = {}
;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版
「全文完,既然看到这里了,如果觉得不错,随手点个赞和“在看”吧。」
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。