题解 | #实现二叉树先序，中序和后序遍历#javascript递归和迭代解法

NC45 实现二叉树先序，中序和后序遍历

中等

知识点：栈、树、哈希 描述 给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围：0 \le n \le 10000≤n≤1000，树上每个节点的val值满足 0 \le val \le 1000≤val≤100 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n) 样例解释： 如图二叉树结构 示例1 输入： {1,2,3} 复制 返回值： [[1,2,3],[2,1,3],[2,3,1]] 复制 说明： 如题面图

1. 递归

思路：

递归较简单，对前序根左右、中序左根yo右、后序左右根的规律设计递归即可，代码如下：

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
function threeOrders( root ) {
    // write code here
    let arr1 = new Array(), arr2 = new Array(), arr3 = new Array();
    preorder(root, arr1);
    inorder(root, arr2);
    postorder(root, arr3);
    return [arr1, arr2, arr3];
}
function preorder(root, arr1) {
    if(!root) return;
    arr1.push(root.val);
    preorder(root.left, arr1);
    preorder(root.right, arr1);
}
function inorder(root, arr2) {
    if(!root) return;
    inorder(root.left, arr2);
    arr2.push(root.val);
    inorder(root.right, arr2);
}
function postorder(root, arr3) {
   if(!root) return;
    postorder(root.left, arr3);
    postorder(root.right, arr3);
    arr3.push(root.val);
}
module.exports = {
    threeOrders : threeOrders
};

2. 迭代

思路：

前序遍历是根左右，由于根节点是压进去立刻又出栈，真正的压栈顺序是先右再左，代码如下

function preorder(root, arr1) {
    if(!root) return;
    let stack = [];
    stack.push(root);
    while(stack.length) {
        let x = stack.pop();
        arr1.push(x.val);
        if(x.right) stack.push(x.right);
        if(x.left) stack.push(x.left);
    }
}

后序遍历是左右根，由于前序是根左右，所以可看做是前序变换压栈顺序变成根右左后，再把数组倒置过来变成左右根，因此真正的压栈顺序是先左再右，代码如下

function postorder(root, arr3) {
    if(!root) return;
    let stack = [];
    stack.push(root);
    while(stack.length) {
        let x = stack.pop();
        arr3.push(x.val);
        if(x.left) stack.push(x.left);
        if(x.right) stack.push(x.right);
    }
    arr3.reverse();
}

中序遍历是左根右，思路是一直将左孩子压栈，一直到空位置就出栈，即弹出空结点的父亲，输出值后，再将右孩子压栈，重复，直到栈空

function inorder(root, arr2) {
    if(!root) return;
    let stack = [];
    while(root || stack.length) {
        if(root) {
            stack.push(root);
            root = root.left;
        }
        else {
            root = stack.pop();
            arr2.push(root.val);
            root = root.right;
        }
        
    }
}