贰.1.4 二叉树的遍历

对于给定的二叉树如图:

贰.1.4.1 前序遍历

定义

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。

文首的图,前序遍历的结果是:12457836

题目

给定一个二叉树,返回它的 前序 遍历。示例:

输入: [1,null,2,3]的树 1 \ 2 / 3 输出: [1,2,3]

代码

递归解法:

/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let result=[];
(function func(root){
if(root)
result.push(root.val);
if(root&&root.left){
func(root.left);//递归
}
if(root&&root.right){
func(root.right);//递归
}
})(root);
return result;
};

迭代解法:

/**
* @param {TreeNode} root
* @return {arr[]}
*/
var preorderTraversal = function (root) {
let stack = [root];
let arr = [];
while (stack.length > 0) {//循环迭代
let node = stack.pop();
node && arr.push(node.val); // node不为空时,向arr中推入节点值
node && node.right && stack.push(node.right); //关键点:模拟栈,后入先出,故先压右节点
node && node.left && stack.push(node.left); // 关键点:后入先出,后压左节点
}
return arr
};

贰.1.4.2 中序遍历

定义

中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。

文首的图,中序遍历的结果是:42758136

题目

//略

贰.1.4.3 后序遍历

定义

后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。

文首的图,后序遍历的结果是:47852631

题目

//略

贰.1.4.4 层序遍历

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

题目

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

思路

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

代码

//用一个多维数组表示树
let tree=[[1,]];
((T)=>{
let queue=[];
//todo
})(tree);

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

其实深度优先遍历也就是前序遍历,广度优先遍历就是层序遍历。