二叉树遍历有三种遍历方式，前、中、后。这些不多介绍了。

如果使用代码实现有可以有多种不同的方式。本文着重讲解这几种方式，并且探究不同方式的时间和空间复杂度。

定义二叉树

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

前序遍历

递归法

1
2
3
4
5
6
7
public static void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
        return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pollLast();
        output.add(node.val);
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            stack.add(node.left);
        }
    }
    return output;
}

莫里斯法

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
public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<Integer> output = new LinkedList<>();

    TreeNode node = root;
    while (node != null) {
        if (node.left == null) {
            output.add(node.val);
            node = node.right;
        }
        else {
            TreeNode predecessor = node.left;
            while ((predecessor.right != null) && (predecessor.right != node)) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                output.add(node.val);
                predecessor.right = node;
                node = node.left;
            }
            else{
                predecessor.right = null;
                node = node.right;
            }
        }
    }
    return output;
}

中序遍历

递归法

1
2
3
4
5
6
7
public static void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);
        System.out.println(root.val);
        inorderTraversal(root.right);
    }
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.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
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ldr = new ArrayList<Integer>();
    TreeNode cur = root;
    TreeNode pre = null;
    while(cur!=null){
        if(cur.left==null){//左子树为空，输出当前节点，将其右孩子作为当前节点
            ldr.add(cur.val);
            cur = cur.right;
        }
        else{
            pre = cur.left;//左子树
            while(pre.right!=null&&pre.right!=cur){//找到前驱节点，即左子树中的最右节点
                pre = pre.right;
            }
            //如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
            if(pre.right==null){
                pre.right = cur;
                cur = cur.left;
            }
            //如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
            if(pre.right==cur){
                pre.right = null;
                ldr.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return ldr;
}

后序遍历

递归法

1
2
3
4
5
6
7
public static void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.println(root.val);
    }
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
        return output;
    }
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pollLast();
        output.addFirst(node.val);
        if (node.left != null) {
            stack.add(node.left);
        }
        if (node.right != null) {
            stack.add(node.right);
        }
    }
    return output;
}

莫里斯法

1
2


总结

时间复杂度 空间复杂度
递归
迭代
莫里斯