2.1.4.md

贰.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 深度优先与广度优先遍历

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