leetcode145：二叉树的后序遍历

[sisterAn]

给定一个二叉树，返回它的 后序 遍历。

示例:

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

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

附赠leetcode地址：leetcode

[7777sea]

var postorderTraversal = function(root) {
    let res = []  // 用来存储后序遍历节点的值
        stack = []  
        cur = root

    var lastVisitedNode = null;
    while(cur || stack.length > 0) {
        if(cur !== null){
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            if(cur.right === null || lastVisitedNode === cur.right) {
                res.push(cur.val);
                lastVisitedNode = cur;
                cur = null;
            } else {
                stack.push(cur);
                cur = cur.right;
            }
        }
    }
    return res;
};

[plane-hjh]

后序遍历

• 后序遍历：先访问左节点，再访问右节点，最后访问根节点

递归版本

// 递归
const postOrderTraverse = (root) => {
    let list = []

    const postOrder = (node) => {
        if(!node) {
            postOrder(node.left)
            postOrder(node.right)
            list.push(node.val)
        }
    }

    postOrder(root)

    return list
}

迭代版本

// 非递归
const postOrderTraverseUnRecur = (root) => {
    let list = []
    if(root !== undefined) {
        let s1 = []
        let s2 = []

        s1.push(root)

        while(s1.length !== 0) {
            head = s1.pop()
            s2.push(head)

            if(head.left !== undefined) {
                s1.push(head.left)
            }

            if(head.right !== undefined) {
                s1.push(head.right)
            }
        }

        while(s2.length !== 0) {
            var item = s2.pop()
            list.push(item.val)
        }
    }

    return list
}

[luweiCN]

var postorderTraversal = function (root) {
  if (root === null) return [];
  let stack = [root];
  let res = [];
  while (stack.length) {
    let current = stack.pop();
    if (current === null) continue;
    if (!current.visited) {
      current.visited = true;
      stack.push(current, current.right, current.left);
    } else {
      res.push(current.val);
    }
  }

  return res;
};

[syc666]

const fun = (tree) => {
    //迭代
    let res = []
    const stack = []
    if(tree) stack.push(tree)
    while(stack.length>0){
        const chTree = stack.pop()
        if(chTree.left) stack.push(chTree.left)
        if(chTree.right) stack.push(chTree.right)
        res.unshift(chTree.val)
    }
    return res
}

[sisterAn]

递归实现

// 后序遍历
const postorderTraversal = function(root) {
    let result = []
    var postorderTraversalNode = (node) => {
        if(node) {
            // 先遍历左子树
            postorderTraversalNode(node.left)
            // 再遍历右子树
            postorderTraversalNode(node.right)
            // 最后根节点
            result.push(node.val)
        }
    }
    postorderTraversalNode(root)
    return result
};

迭代实现

解题思路： 后序遍历与前序遍历不同的是：

• 后序遍历是左右根

• 而前序遍历是根左右

如果我们把前序遍历的 list.push(node.val) 变更为 list.unshift(node.val) （遍历结果逆序），那么遍历顺序就由 根左右 变更为 右左根

然后我们仅需将 右左根 变更为 左右根 即可完成后序遍

// 后序遍历
const postorderTraversal = (root) => {
    const list = [];
    const stack = [];
    
    // 当根节点不为空的时候，将根节点入栈
    if(root) stack.push(root)
    while(stack.length > 0) {
        const node = stack.pop()
        // 根左右=>右左根
        list.unshift(node.val)
        
        // 先进栈左子树后右子树
        // 出栈的顺序就变更为先右后左
        // 右先头插法入list
        // 左再头插法入list
        // 实现右左根=>左右根
        if(node.left !== null) {
            stack.push(node.left)
        }
        if(node.right !== null) {
            stack.push(node.right)
        }
    }
    return list
}

复杂度分析：

空间复杂度：O(n)

时间复杂度：O(n)

leetcode

[2hangJing]

后序遍历：l -> r -> m，通过左右镜像得到：m -> r -> l。所以只用实现 根 -> 右 -> 左，再通过 unshift 倒叙输出到数组中即实现后续遍历。

let postorderTraversal_iteration = (tree)=>{
    let list = [];
    // 根结点入栈
    let stack = [tree];
    while(stack.length>0){
        // 栈顶元素出栈
        let node = stack.pop();
        if(node === null) continue;
        // 通过倒叙输出将 根->右->左 转换成 左->右->根（后续遍历）
        list.unshift(node.val);
        stack.push(node.left);
        stack.push(node.right);
    }  
    return list;
}