js实现二叉树的先序、中序、后序遍历，递归和非递归方法

骑猪看日落 2022-09-08 00:21 199阅读 0赞

//递归实现
    function TreeNode(x){
        this.val=val;
        this.left=null;
        this.right=null;
    }
    // 递归方法
    function threeOrders(root){
        let preArray=[],middleArray=[],lastArray=[];
        //先序遍历：根、左、右
        function preOrder(root){
            if(root){
                preArray.push(root.val);
                preOrder(root.left);
                preOrder(root.right);
            }
        }
        //中序遍历 ： 左 根 右   
        function inOrder(root){
                if(root){
                    inOrder(root.left)
                    middleArray.push(root.val);
                    inOrder(root.right);
                }
        }
        //后序遍历：左右根
        function lastOrder(root){
            if(root){
                lastOrder(root.left);
                lastOrder(root.right);
                lastArray.push(root.val);
            }
        }
        preOrder(root);
        inOrder(root);
        lastOrder(root);
        return [preArray,middleArray,lastArray]
    }
    
    
    //非递归实现
    function threeOrders(root){
        //非递归算法实现先序遍历二叉树，根左右，所以向数组中push一个元素
        function preOrder(root){
            let res=[],
            stack=[root];
            while(stack.length>0){
                let node=stack.pop();
                res.push(node.val);
                if(node.left){
                    stack.push(node.left);
                }
                if(node.right){
                    stack.push(node.right);
                }
    
            }
            return res;
        }
        //非递归算法 实现中序遍历二叉树   首先遍历找到最深层的左子树，
        function inOrder(root){
            let res=[],
                stack=[];
                while(root||stack.length>0){
                    while(root){
                        stack.push(root);
                        root=root.left;
                    }
                    root=stack.pop();
                    res.push(root.val);
                    root=root.right;
                }
                return res;
        }
        // 非递归算法实现后序遍历二叉树， 和先序遍历二叉树类似，唯一区别是向数组中unshift元素，先push左再push右
        function lastOrder(root){
            let res=[],
            stack=[root];
            while(stack.length>0){
                let node=stack.pop();
                res.unshift(node.val);
                if(node.left){
                    stack.push(node.left);
                }
                if(node.right){
                    stack.push(node.right);
                }
            }
            return res;
        }
    }

由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利用一个辅助栈来进行每个节点的存储打印，所以每个节点都要进栈和出栈，不过是根据那种遍历方式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数。