勿助勿忘，深造自得

0%

二叉树的中序遍历

发表于 更新于 分类于

二叉树的中序遍历的实现

应用场景

可以用来做表达式树

实现方式

栈

  1. 遇到一个结点，就把它压栈，并去遍历它的左子树；
  2. 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
  3. 然后按其右指针再去中序遍历该结点的右子树；；

    时间复杂度：O(n)。
    空间复杂度：O(n)

递归

  1. 中序遍历访问左子树；
  2. 访问根节点；
  3. 中序遍历访问右子树；

时间复杂度：O(n)。递归函数 T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1。
空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。

源码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中序遍历：左子树---> 根结点 ---> 右子树
 */
class BTreeInorderTranversal94 {
    /***
     * 子树遍历-stack实现
     * @param root 根节点
     */
    public static List<Integer> traversalTreeInOrder_stack(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        //遍历所有路径，直到某条路径没有叶子节点or栈已空时，结束遍历
        while (curr != null || !stack.isEmpty()) {
            //树遍历左子树并入栈，到叶子节点停止
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            //叶子节点出栈
            curr = stack.pop();
            nodes.add(curr.val);
            //当前节点，从右子树遍历
            curr = curr.right;
        }
        return nodes;
    }

    /***
     * 子树遍历-recurse实现
     * @param nodes 遍历结果数组
     * @param root 根节点
     */
    public static void traversalTreeInOrder_recurse(List<Integer> nodes, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            //左子树遍历
            traversalTreeInOrder_recurse(nodes, root.left);
        }
        //根节点
        nodes.add(root.val);
        if (root.right != null) {
            //右子树遍历
            traversalTreeInOrder_recurse(nodes, root.right);
        }
    }

    /***
     * 树节点
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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