前端内参
搜索文档…
贰.1.4 二叉树的遍历
对于给定的二叉树如图:
Could not load image

贰.1.4.1 前序遍历

定义

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
文首的图,前序遍历的结果是:12457836

题目

给定一个二叉树,返回它的 前序 遍历。示例:
输入: [1,null,2,3]的树 1 \ 2 / 3 输出: [1,2,3]

代码

递归解法:
1
/**
2
* @param {TreeNode} root
3
* @return {number[]}
4
*/
5
var preorderTraversal = function(root) {
6
let result=[];
7
(function func(root){
8
if(root)
9
result.push(root.val);
10
if(root&&root.left){
11
func(root.left);//递归
12
}
13
if(root&&root.right){
14
func(root.right);//递归
15
}
16
})(root);
17
return result;
18
};
Copied!
迭代解法:
1
/**
2
* @param {TreeNode} root
3
* @return {arr[]}
4
*/
5
var preorderTraversal = function (root) {
6
let stack = [root];
7
let arr = [];
8
while (stack.length > 0) {//循环迭代
9
let node = stack.pop();
10
node && arr.push(node.val); // node不为空时,向arr中推入节点值
11
node && node.right && stack.push(node.right); //关键点:模拟栈,后入先出,故先压右节点
12
node && node.left && stack.push(node.left); // 关键点:后入先出,后压左节点
13
}
14
return arr
15
};
Copied!

贰.1.4.2 中序遍历

定义

中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
文首的图,中序遍历的结果是:42758136

题目

//略

贰.1.4.3 后序遍历

定义

后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。
文首的图,后序遍历的结果是:47852631

题目

//略

贰.1.4.4 层序遍历

文首的图,层序遍历的结果是:12345678

题目

文首的二叉树,请你返回其按 层序遍历 得到的节点值(即逐层地,从左到右访问所有节点)。 返回其层次遍历结果数组: [[1],[2,3],[4,5,6],[7,8]]

思路

利用队列这个数据结构,将每层的节点放进队列,遍历完当前层的节点之后,再将子节点放到队列进行遍历,直到遍历完所有叶节点。

代码

1
//用一个多维数组表示树
2
let tree=[[1,]];
3
4
((T)=>{
5
let queue=[];
6
//todo
7
8
})(tree);
Copied!

贰.1.4.5 深度优先与广度优先遍历

其实深度优先遍历也就是前序遍历,广度优先遍历就是层序遍历。
最近更新 1yr ago