DarkYellowCat's Blog

分享技术与思考

0%

'二叉树的遍历'

发表于 更新于 分类于

以中序遍历进行介绍

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Recursion {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void preorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

2.迭代

用栈来实现二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Iteration {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = 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();
            ans.add(curr.val);      // 访问
            curr = curr.right;      // 转向右子树
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

3.Mirris

对于当前节点 curr：

  • 如果 没有左子树：直接访问 curr，然后进入右子树。
  • 如果 有左子树：
    找到 curr 的前驱节点（即左子树中的最右节点，记为 pre）。
    • 如果 pre.right == null：说明第一次访问，建立线索 pre.right = curr，然后进入左子树。
    • 如果 pre.right == curr：说明左子树已遍历完，断开线索（恢复原树结构），访问 curr，然后进入右子树。
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
class Mirris {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                ans.add(curr.val);
                curr = curr.right;
            } else {
                // 找到左子树的最右节点（前驱）
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    // 建立线索
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    // 线索已存在，说明左子树已遍历完
                    pre.right = null; // 恢复树结构
                    ans.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

4.测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Recursion recursion = new Recursion();
        List<Integer> res1 = recursion.inorderTraversal(root);
        System.out.println("Recursion: " + res1);

        Iteration iteration = new Iteration();
        List<Integer> res2 = iteration.inorderTraversal(root);
        System.out.println("Iteration: " + res2);

        Mirris mirris = new Mirris();
        List<Integer> res3 = mirris.inorderTraversal(root);
        System.out.println("Mirris: " + res3);
    }
}

给出的树结构：

1
2
3
4
5
1
 \
  2
 /
3

中序遍历（左 → 根 → 右）：[1, 3, 2]