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

• 难度：Medium
• 标签：递归 DFS
• 题意解析：二叉树的中序排列实现，流程是 左-》根-》右.

刷题思路

• [x] 模板递归（DFS）
• [x] 含状态的模板迭代法(DFS)

方法 1 模板递归（DFS）

• 思路：用数组res存储结果，递归方法以节点node和结果数组res作为参数.
• 复杂度：
  • 时间：遍历整个二叉树故时间复杂度为 O(n)
  • 空间：结果数组是必备空间所以不占复杂度，占空间的是递归调用栈，近似于树的深度h
    • 当树是平衡二叉树时，树的深度为logn，故其空间复杂度为O(logn)；
    • 当树严重左偏或者右偏的时候，树的深度为n，故其空间复杂度为O(n);
• 结果:
  • 执行用时：88 ms, 在所有 JavaScript 提交中击败了38.35%的用户
  • 内存消耗：37.4 MB, 在所有 JavaScript 提交中击败了21.07%的用户

var inorderTraversal = function(root) {
    let res = []
    recursion(root, res)
    return res
};

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

方法 2 含状态的模板迭代法(DFS)

• 思路: 用栈辅助存储未处理的值,每个节点加上标志位flag,标志位的作用是标志节点的身份是否为处理完成的节点.
• 复杂度:
  • 时间: O(n). 耗时点在于每个结点会经历两次遍历(塞入->弹出->标记->塞入->弹出)，也就是时间复杂度是O(2n);
  • 空间: O(n). 分析同上.
• 结果：
  • 执行用时：88 ms, 在所有 JavaScript 提交中击败了38.35%的用户
  • 内存消耗：37 MB, 在所有 JavaScript 提交中击败了63.94%的用户

var inorderTraversal = 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) // flag=true 表示这次要访问的是该节点，可以打印或者做其他处理
        } else { // flag=false 表示暂时没空访问该节点，只能先将其入栈等待之后处理
            // 中序顺序：左-》根-》右
            // 进栈顺序：右-》根-》左(与出栈顺序相反)
            if (node.right) stack.push(node.right)
            node.flag = true // 先标记再进栈
            stack.push(node)
            if (node.left) stack.push(node.left)
        }
    }
    return res
};

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