94. 二叉树的中序遍历

[Geekhyt]

原题链接

周树人先生曾经说过：学好树，数据结构与算法你就掌握了一半！

食堂老板(童欧巴)：就算我们作为互联网浪潮中的叶子结点，也需要有蚍蜉撼树的精神，就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人，但你总不能为了成为一个普通人而终其一生吧。

今日菜谱，蚂蚁上树，下面介绍一下演员。

树的相关名词科普

• 根节点
• 叶子节点
• 父节点
• 子节点
• 兄弟节点
• 高度
• 深度
• 层

A 是 根节点。C、D、F、G 是 叶子节点。A 是 B 和 E 的 父节点。B 和 E 是 A 的 子节点。B、E 之间是 兄弟节点。

高度、深度、层 如上图所示。

为了方便理解记忆，高度 就是抬头看，深度 就是低头看。

与 高度、深度 不同，层 类比盗梦空间里的楼，楼都是从 1 层开始计算，盗梦空间中的楼颠倒过来，从上往下。

中序遍历：先打印当前节点的左子树，再打印当前节点，最后打印当前节点的右子树 (CBDAFEG)

const inorderTraversal = function(root) {
    const result = [];
    function pushRoot(root) {
        if (root !== null) {
            if (root.left !== null) {
                pushRoot(root.left);
            }
            result.push(root.val);
            if (root.right !== null) { 
                pushRoot(root.right);
            }
        }
    }
    pushRoot(root);
    return result;
};

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

[yuetong3yu]

遍历实现

中序的二叉树遍历相较于前序和后序略有不同

var inorderTraversal = function(root) {
    const ret = []
    if (!root) return ret
    const stack = []
    // 利用一个游标
    let cur = root
    while(cur || stack.length) {
        // dfs往最左节点遍历
        while(cur) {
            stack.push(cur)
            cur = cur.left
        }
        // 此时游标一定停在最左节点空节点
        // 推出栈顶元素
        cur = stack.pop()
        ret.push(cur.val)
        // 当右节点为空的时候，这一步给的是null
        // 右节点存在的时候，上面的cur一定是一个root节
        cur = cur.right
    }
    return ret
};