94. 二叉树的中序遍历

方法一：递归 (最简单的)

    List<Integer> nodeList = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return nodeList;
        }

        inorderTraversal(root.left);

        nodeList.add(root.val);

        inorderTraversal(root.right);

        return nodeList;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二： 迭代

遍历到对应节点，将对应的节点压入栈中，遍历到头之后，开始将栈中的节点弹出来，进行操作：（中序遍历）

从根节点开始访问，若根节点不为空(或者根节点为空时，但是栈中还有节点，弹出栈中的节点，将其作为根节点进行循环操作–> 最终会弹出来 真正的根节点，之后会对其右子树进行操作！！！)，将该节点入栈
然后 访问其左子树，执行 root = root.left
如若没有左子树直接访问右子树 : 执行 root = root.right

方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

public List<Integer> inorderTraversal2(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    Deque<TreeNode> stk = new LinkedList<TreeNode>();
    while (root != null || !stk.isEmpty()) {
        while (root != null) {
            stk.push(root);
            root = root.left;
        }

          // Question1：前面的额循环体跳出来之后，root===null,下面还怎么对 节点的左右子树（节点）进行操作呢？

        root = stk.pop();
        res.add(root.val);

        
          // Question2：前面传入的 root 代表的就是最左侧的节点了，但是如果该节点没有右节点，那下面的 root 不就是成了 null 了，还怎么操作呢？而且前面的节点的右子树也没有遍历呢？
        
        root = root.right;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• Question1：前面的额循环体跳出来之后，root===null,下面还怎么对 节点的左右子树（节点）进行操作呢？

• Answer1: 前面的额循环的作用主要是将指针达到最左边的节点上面，并将前面的节点进栈，并不是处理 root 的
  真正的对于 root 的赋值的操作，是下面的 这一句：将栈中的元素给弹出来赋值给 root (这才是真正的最左侧的节点)

• Question2：
  前面传入的 root 代表的就是最左侧的节点了，但是如果该节点没有右节点，那下面的 root 不就是成了 null 了，还怎么操作呢？而且前面的节点的右子树也没有遍历呢？

• Answer2:
  首先，对于 root 为空这个问题，虽然在这里为空了，但是我们的 大 while 并不会停止，因为循环条件是 (root != null || !stk.isEmpty())，也就是说，当我们的栈不为空的时候，循环还是为继续执行的，只不过这个时候 里面的 小 while 不执行了而已，–> 直接执行后面的 出栈和给 root 重新赋值的操作 --> 一直到 真正的根节点出栈，之后 root = root.right 访问真正的根节点的右子树 ==> 直到最后，root 为空而且 栈为空的时候 全部迭代完成，输出 res 即为结果！！！

方法三： Morris 遍历算法（线索树）

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 x）：

1. 如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x = x.right。
2. 如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。

• 如果 predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 x = x.left。
• 如果 predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将 predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 x = x.right。

3. 重复上述操作，直至访问完整棵树。

其实整个过程我们就多做一步：假设当前遍历到的节点为 x，
将 x 的左子树中最右边的节点的右孩子指向 x，这样在左子树遍历完成后我们通过这个指向走回了 x，
且能通过这个指向知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。

复杂度分析

时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 O(2n)=O(n)O(2n)=O(n)。
这里的时间复杂度虽然是O(n),但是实际上是 O(2n) 化简过来的，所以使用该方法的时候，花费的的时间可能会相对较长一点点

空间复杂度：O(1)。

public List<Integer> inorderTraversal3(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    TreeNode predecessor = null;

    while(root!=null){
        if(root.left != null){
             // predecessor 节点就走向左节点，然后一直向右走到头（走至无法走为止）
            predecessor = root.left;

             // 确保右节点不为空，而且该节点的右节点没有被标记过
            while(predecessor.right != null && predecessor.right != root){
                predecessor = predecessor.right;
            }

             // 出循环--到达最右侧，让 predecessor 的右指针指向 root，继续遍历左子树
            if(predecessor.right == null){
                 最右侧节点链接到其想对的根节点
                predecessor.right = root;
                 继续遍历左子树
                root = root.left;
            }
             // 如果左子树均已经访问完毕，我们就需要断开连接
            else{
                res.add(root.val);
                 // 这一步：将我们链接的 指针 给置空 ---> 恢复原来的数据结构，不改变原来的二叉树结构
                predecessor.right = null;
                //  访问右节点
                root = root.right;

            }
             // 如果没有左孩子，则直接访问右孩子
        }else{
            res.add(root.val);
            root = root.right;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38