二叉树的中序遍历 [递归 & 迭代]

前言

中序遍历，递归进行左中右遍历，非常简单高效。迭代的方式稍显麻烦，不过也是遵循左中右遍历的原则。而在迭代方法中，将二叉树原地修改成双向循环链表，再进行遍历，则需要栈空间，就可以完成迭代版的中序遍历。

一、二叉树的中序遍历

二、递归 & 迭代

1、递归版

	// Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
	List<Integer> ans = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(null == root) return ans;

        inorderTraversal(root.left);

        ans.add(root.val);

        inorderTraversal(root.right);

        return ans;
    }  
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

2、迭代（断左子树版）

// 断链法，按自己独立思考复杂的逻辑来的。
    // 靠peek()节点遍历。
    public List<Integer> inorderTraversal2(TreeNode root) {
        if (null == root) return ans;

        Stack<TreeNode> sk = new Stack<>();
        sk.push(root);

        while (!sk.isEmpty()) {
            // while不断left压栈。
            while (sk.peek().left != null) {
                TreeNode left = sk.peek().left;
                sk.peek().left = null;
                sk.push(left);
            }
            // 一旦不断left到底了，至少说明没有左孩子了（null孩子不加入！），直接访问当前节点。
            ans.add(sk.peek().val);
            // if将右节点当作一个子树来对待，重新进入循环进行left压栈。
            if (sk.peek().right != null) {
                TreeNode right = sk.peek().right;
                sk.pop().right = null;
                sk.push(right);
            } else sk.pop();
        }
        return ans;
    }
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

3、迭代（root迭代版）

// 不断链，而是更新root！
    // 靠root节点遍历。
    public List<Integer> inorderTraversal3(TreeNode root) {
        if (null == root) return ans;

        Stack<TreeNode> sk = new Stack<>();

        while (root != null || !sk.isEmpty()) {
            // 遍历左节点。
            while (root != null) {
                sk.push(root);

                root = root.left;
            }
            // 靠着栈轨迹，把root拉回来。
            root = sk.pop();
            // 访问根节点。
            ans.add(root.val);
            // 靠着栈轨迹的root，寻找右子树。
            root = root.right;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、mirror（O(1)空间版）

// mirror法：将左子树最右孩子的指针指向该节点，即让前驱节点的next指向自己，形成左中右的单向链，让空间复杂度降到O(1)
    public List<Integer> inorderTraversal4(TreeNode root) {
        if (null == root) return ans;
        while (root != null) {
            // 让root的前驱指向自己，前驱在左子树的最右节点上。
            if (root.left != null) {
                TreeNode p = root.left;
                // p.right != root，防止重复访问左边，导致死循环。
                while (p.right != null && p.right != root) p = p.right;

                if (p.right == null) {
                    p.right = root;
                    // 继续遍历左子树，设置好right指针。
                    root = root.left;
                }
                // 说明p.right == root，说明左子树已经遍历完了，访问自己 + 访问右子树。
                // 注：如果想要不修改树结构，即可把right断掉。
                else {
                    ans.add(root.val);

                    root = root.right;
                    // 可把right断掉，保持原来的树结构。
                    p.right = null;
                }
            } else {
                ans.add(root.val);

                root = root.right;
            }
        }
        return ans;
    }
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

总结

1）二叉树的遍历，遵循左中右原则，递归 / 迭代都可。一题多解，对问题中涵盖的知识点才能融汇贯通，比如这里对左中右遍历的理解，在迭代情况下get值的时机，对二叉树这种递归结构 的理解，对二叉树&双向链表的关系，通过mirror联想到线索二叉树等等。

2）迭代版中的mirror版，可以将空间复杂度降到O(1)。需要理解临时修改right指针，把二叉树当成双向链表看待，也可以想象一下二叉搜索树的样子，是否也是同个原理！

3）coding要实际，不能只看看，比如这里独立思考的断链法和root法还是在思想上有很大不同，虽然root法很容易理解，但不是我能输出的！比如root法中while(root != null || !sk.isEmpty())为什么要两个条件，又为什么要或运算，这都需要实际coding并加强理解！比如mirror法为什么空间O(1)，修改right指针的本质？为什么每个节点会被访问两次？在mirror版下在那两种情况下访问节点？left == null时可访问，有环的情况可访问，一种是左孩子为null，一种是左孩子被访问过，不用再访问了。

4）每次访问了，就root = root.right，左子树就不用过问了，为什么这样，需要深刻理解树的递归结构，每一个节点都是root！

参考文献

[1] LeetCode 二叉树的中序遍历

[2] LeetCode 二叉树的中序遍历 mirror版