树 后序遍历 JS 算法 头条腾讯前端面经

算法题目

实现树的后序遍历

前提知识点:
了解数据结构: 树
了解什么是树的后序遍历

算法详解

这题考查了最基础的数据结构,树 和遍历算法

我们先看下什么是树【我们以二叉树为例,每个节点最多有两个子节点】
树结构

如上是我们经常描述的数据结构,它是一个类似这样的结构,类似倒立的树
这里的跟节点是 g,每个节点都有子节点,每个子节点也有它的子节点,这样形成一个递归结构

后序遍历的顺序是 a b e c d f g
也就是 先左子节点,其次右子节点,最后根

下面我们用算法来得到这个后序序列
假设用来描述树的结点的数据结构是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 这里先简单描述节点的数据结构类型
* 节点存储的值是 value
* 左节点指向为 leftNode
* 右节点指向为 rightNode
*/
function TreeNode(value, leftNode, rightNode) {
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
}

/**
* 后序遍历
*/
function postOrder(headNode, seqArr) {
if (!headNode) {
return
}

postOrder(headNode.leftNode, seqArr);
postOrder(headNode.rightNode, seqArr);
seqArr.push(headNode.value);
}

var seq = []
var headNode = new TreeNode('g');
// 假设这里是构建树
create(headNode)

postOrder(headNode, seq)

console.log(seq);

最后seq得到的就是后序遍历序列了

这是递归版本的遍历算法,递归算法看起来简洁明了,逻辑清晰,但是由于递归占用栈空间,导致递归层数太多的话,容易导致栈爆。

因此有能力的同学可以思考下非递归版本的实现

同时,关于树的遍历算法相关的,还有很多其他场景的,学会理解为先,融会贯通

树的先序遍历 – BAT大厂面试题
树的中序遍历 – BAT大厂面试题

 
更多前端面试题和算法题,请搜索微信小程序 前端面试精华
Front-end interview essence
Front-end interview essence

坚持原创技术分享,谢谢鼓励我继续创作!