145.二叉树的后序遍历

145.二叉树的后序遍历

1h

中序遍历的顺序是 左 - 右 - 中

递归

用递归非常容易

var postorderTraversal = function(root) {
    var res = []
    if (!root)
    return res
    var travel = function (node) {
        node.left && travel(node.left)
        node.right && travel(node.right)
        res.push(node.val)
    }
    travel(root)
    return res
};

迭代

1. 根节点入栈
2. 判断是否可以出栈，如果能，则记录自己为上一个出栈节点，出栈
3. 不能出栈，分别将右节点和左节点入栈
4. 重复第二个步骤

var postorderTraversal = function(root) {
    var stack = [root]
    var res = []
    if (!root) {
        return res
    }
    var pre = root
    while(stack.length) {
        var node = stack[stack.length - 1]
        // 当节点的 左 / 右 节点是上一个被输出的节点，代表左右节点都已经被输出过（因为后序遍历根节点在最后）
        if ( (!node.left && !node.right) || (node.left === pre || node.right === pre)) {
             // 只有在没有 左右节点，或者 左右节点都输出过时才可以输出
            node = stack.pop()
            pre = node
            res.push(node.val)
        } else {
            if (node.right) {
                stack.push(node.right)
            }
            if(node.left) {
                stack.push(node.left)
            }
        }
    }
    return res
};

总结

虽然，做完了二叉树的前中后序遍历，但是我有预感用不了多久就会忘记，特别是中序遍历和后序遍历，我完全没有找到两者有什么共同点，所以随后会做一下总结。