144 二叉树后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

题解

有递归和非递归的两种解法

递归解法

第一种方法就是递归，这种方法简单易懂，直接上代码：

var postOrderRecursive = function(root) {
    var postOrderInner = function(root, result) {
        if(!root) {
            return
        }
        postOrderInner(root.left, result)
        postOrderInner(root.right, result)
        result.push(root.val)
    }

    const result = []
    postOrderInner(root, result)
    return result
}

非递归解法

非递归解法其实和前序遍历的非递归方法类似，前序遍历的非递归方法是根左右，那我们可以在递归的时候变成 根右左。然后遍历完后整体反转，就成了 左右根。

所以可以写出以下代码

var postOrderStack = function(root) {
    // 4, 5, 2, 6,7, 3, 1
    //前序遍历 根左右 后序遍历 左右根
    // 前序遍历 换个位置 根右左， 然后整体镜像 ，左右根
    const result = []
    const stack = []
    if(!root) {
        return result
    }
    stack.push(root)
    while(stack.length) {
        const current = stack.pop()
        result.push(current.val)
        // 先入 左
        if(current.left) {
            stack.push(current.left)
        }
        // 在入 右
        if(current.right) {
            stack.push(current.right)
        }
    }
    // 最后翻转
    result.reverse()

    return result
}