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

• 难度：Medium
• 标签：

刷题思路

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

方法 1 模板递归法（DFS）

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

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

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

方法 2 模板迭代法（DFS）

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

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

优化版本，减少一轮循环：

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

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