二叉树的后序遍历 (opens new window)

• 难度：Medium
• 标签：

刷题思路

• [x] 模板递归法（DFS）
• [x] 模板迭代法（DFS）

方法 1 模板递归法（DFS）

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)

var postorderTraversal = function(root) {
    const res = []
    recursion(root, res)
    return res
};

function recursion (node, res) {
    if (!node) return
    if (node.left) recursion(node.left, res)
    if (node.right) recursion(node.right, res)
    res.push(node.val)
}

方法 2

• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：92 ms, 在所有 JavaScript 提交中击败了25.98%的用户
  • 内存消耗：37.3 MB, 在所有 JavaScript 提交中击败了48.96%的用户

var postorderTraversal = function(root) {
    if(!root) return []
    const stack = [root]
    const res = []
    while (stack.length > 0) {
        const node = stack.pop()
        if (node.flag) {
            res.push(node.val)
        } else {
            node.flag = true
            stack.push(node)
            if (node.right) stack.push(node.right)
            if (node.left) stack.push(node.left)
        }
    }
    return res
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~