美文网首页
遍历二叉树

遍历二叉树

作者: wwmin_ | 来源:发表于2019-08-18 09:16 被阅读0次

    总结了二叉树的先序、中序、后序遍历算法,分别给出了这三种算法的递归写法和迭代写法。
    默认数据结构如下:

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    

    先序

    中左右  
    
    
    /**
     * Recursive 递归
     * 纯函数
     */
    var preorderTraversal = function(root) {
        var r = [];
    
        if(!root) return [];
    
        r.push(root.val);
    
        if(root.left)
            r = r.concat(preorderTraversal(root.left));
    
        if(root.right)
            r = r.concat(preorderTraversal(root.right));
    
        return r;
    };
    
    /**
     * iteratively 迭代
     * 思路:首先把根节点入栈,然后迭代以下过程:
     * 出栈,输出这个节点,这个节点的右、左子节点依次入栈
     */
    
    var preorderTraversal = function(root) {
        const stack = [];
    
        stack.push(root);
    
        const traversal = [];
    
        while (stack.length){
            const node = stack.pop();
    
            if (!node){
                continue;
            }
    
            traversal.push(node.val);
    
            stack.push(node.right);
            stack.push(node.left);
        }
    
        return traversal;
    };
    

    中序

    左中右  
    
    
    /**
     * Recursive 递归
     */
    var inorderTraversal = function(root) {
        var r = [];
    
        if(!root) return [];
    
        if(root.left)
            r = r.concat(inorderTraversal(root.left));
    
        r.push(root.val);
    
        if(root.right)
            r = r.concat(inorderTraversal(root.right));
    
        return r;
    };
    
    /*
     * iteratively 迭代
     */
    var inorderTraversal = function(root) {
        let result = [];
        let stack = [];
        let node = root;
    
        while(stack.length > 0 || node !== null) {
            while(node) {
                stack.push(node);
                node = node.left;
            }
    
            if (stack.length !== 0) {
                node = Stack.pop();
                result.push(node.val);
                node = node.right;
            }
        }
    
        return result;
    };
    
    /**
     * iteratively 迭代
     * 思路:首先把根节点入栈,然后迭代以下过程:
     * 1.出栈
     * 2.如果这个节点的子节点没有被Push进栈过(判断方法不写了),依次push右子节点、这个节点、左子节点。
     * 3.判断是否pop并输出。判断方法:leftChild == null || letfChild == 上一次输出的节点 || 上一次输出的节点的rightChild == null 
     */
    var inorderTraversal = function(root) {
        const stack = [];
        const traversal = [];
        let lastOut;
        let thisNode;
    
        stack.push(root);
    
        while (stack.length){
    
            // 1
            thisNode = stack.pop();
    
            if(thisNode == null) {
                continue;
            }
            // 2
            if (thisNode.right != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
                stack.push(thisNode.right);
            }
    
            stack.push(thisNode);
    
            if (thisNode.left != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
                stack.push(thisNode.left);
            }
    
            // 3
            // thisNode = stack[stack.length - 1];
            if( thisNode.left == null || thisNode.left == lastOut || (lastOut && lastOut.right == null)) {
                lastOut = stack.pop();
                traversal.push(lastOut.val);
            }
        }
    
        return traversal;
    };
    

    后序

    左右中  
    
    
    /**
     * Recursive 递归
     */
     var postorderTraversal = function(root) {
        var r = [];
    
        if(!root) return [];
    
        if(root.left)
            r = r.concat(postorderTraversal(root.left));
    
        if(root.right)
            r = r.concat(postorderTraversal(root.right));
    
        r.push(root.val);
        return r;
    };
    
    /**
     * Recursive 递归2
     */
    var postorderTraversal = function(root) {
        let result = [];
        helper(result, root);
    
        return result;
    };
    
    var helper = function(r, root) {
        if(root != null) {
            helper(r, root.left);
            helper(r, root.right);
            r.push(root.val);
        }
    }
    
    /**
     * iteratively 迭代
     */
    var postorderTraversal = function(root) {
        var treeNodeStack = [];
        var node = root;
        var lastVisit = root;
        var res = [];
        while (node != null || treeNodeStack.length>0) {
            while (node != null) {
                treeNodeStack.push(node);
                node = node.left;
            }
    
            node = treeNodeStack[treeNodeStack.length-1];
    
            if (node.right == null || node.right == lastVisit) {
                res.push(node.val);
                treeNodeStack.pop();
                lastVisit = node;
                node = null;
            } else {
                node = node.right;
            }
        }
    
        return res;
    };
    

    相关文章

      网友评论

          本文标题:遍历二叉树

          本文链接:https://www.haomeiwen.com/subject/wxkebqtx.html