94. Binary Tree Inorder Traversal

题干简述：

二叉树中序遍历。

解题思路

二叉树作为最常见的数据结构之一，前中后序遍历是 coder 必学的内容，这里就不在对二叉树前中后序的意义加一阐述了，不是很了解的同学可以自行 google。本文主要讲一下中序遍历的两种解法：BFS 与 DFS。

DFS，大家也很熟悉，深度优先遍历，一般课程中，都是将其作为递归这一概念的实例进行讲解。关于递归函数的规律，大家可以参考我的这一篇文章 337. House Robber III。本题中，由于是中序遍历，故而我们需要在递归遍历 node 的左右子树中间，将 node 的值存入结果数组中。此种解法，本题的难度只有 easy。

那为什么还要单独拿一篇文章来说一下这个问题呢？二叉树的问题，能用 DFS 解决的，大都可以用 BFS 解决，本题用 BFS 广度优先遍历解决的话，难度就上升了不少。不同于 DFS 递归的算法思想，BFS 采用的是迭代的思路。递归时，由于函数一层层的递归执行，我们不需要额外维护当前函数处理的节点的位置信息，反正递归函数结束后，会将结果返回给上一层处理；这样一层一层的返回上去，最终返回给最上层，结束递归时的各层结果一定是正确的。但是，迭代时，是不会这样处理的，因此需要我们通过数组来模拟队列，栈等数据结构，来维护各个节点的位置信息，好根据需要进行操作。本题，我们就需要维护这样的一个栈。

由于是中序遍历，节点处理的顺序必然为 左 - 中 - 右，也就是 node.left - node - node.right。在我们迭代开始时，我们能获取到的节点，只能是根节点 root ，如何确保 root.left -> root -> root.right 这样的存入结果数组的顺序，是解决这题的关键。

首先，我们让左子节点先入栈；

image

此时，2 的左子节点为 null，表明我们这里不可以再进行入栈左子节点了，此时我们可以将已经入栈的左子节点移出，放入 res 中；随后，再将这个入栈的左子节点对应的子树的根节点放入 res 中，此时，这颗子树的中序遍历就做完了一半多了；剩下的，就是如何将其右子节点按照正确的顺序放入 res 中。为了实现这一点，我们需要记住当前我们在操作的是哪一个二叉树；这里，我们可以通过记住当前二叉树的根节点来实现，图中红色的节点，就是我们当前正在操作的树的根节点。眼尖的同学会发现，在 root（1） 入栈后，我们当前没有了根节点了，没有办法走后面的右子节点的操作了，因此我们需要在根节点入栈 res 时，提前更新 当前 root 为原 root（1）的右子节点 3，进入右子树的处理流程中。右子树的处理就和之前一样，当做另一个普通的二叉树处理即可。

image

image

image

除了 DFS 与 BFS 外，还有一个解法，就是 mirrors 遍历。mirrors 遍历的核心思路实际上与 BFS 的并无太大差异，相较于 BFS 解法，它优化了 BFS 对于当前节点左右子树的操作，步骤如下：

假定当前节点为 x

  1. 如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x = x.right
  2. 如果 x 有左孩子，找到 x 子树上最右侧的节点 y，通过 y 的右孩子是否存在，找到当前树，最下最左的子树与对应节点，并根据中序遍历规则，将节点依序存入结果数组中。

有点难理解，可以参考图解 食用。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// DFS
var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    while (root || stack.length) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};

// BFS
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    const dfs = (node) => {
        if (!node) return;
        dfs(node.left);
        res.push(node.val);
        dfs(node.right);
    };
    dfs(root);
    return res;
};

// mirrors
var inorderTraversal = function(root) {
    const res = [];
    let predecessor = null;

    while (root) {
        if (root.left) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root.left;
            while (predecessor.right && predecessor.right !== root) {
                predecessor = predecessor.right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (!predecessor.right) {
                predecessor.right = root;
                root = root.left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res.push(root.val);
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

Q.E.D.

Take it easy