二叉树的递归遍历

发表于 更新于 分类于

算法-二叉树的递归遍历

背景

  • 算法–二叉树的递归遍历

  • 博主以代码随想录算法公开课进行学习

题目

  • 二叉树的递归遍历（前中后序）

思路

  • 二叉树递归遍历核心原理：递归遍历的核心是确定 “访问当前节点” 的时机
    • 前序遍历：中 → 左 → 右（先访问根节点，再递归左子树，最后递归右子树）
    • 中序遍历：左 → 中 → 右（先递归左子树，再访问根节点，最后递归右子树）
    • 中序遍历：左 → 中 → 右（先递归左子树，再访问根节点，最后递归右子树）

代码实现

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
67
import java.util.ArrayList;
import java.util.List;

// 二叉树节点定义（需先定义，否则代码无法运行）
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;
    }
}

class Solution {
    // ==================== 前序遍历：中 → 左 → 右 ====================
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    private void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return; // 递归终止条件：节点为空则返回
        }
        result.add(root.val); // 1. 访问当前节点（中）
        preorder(root.left, result); // 2. 递归遍历左子树（左）
        preorder(root.right, result); // 3. 递归遍历右子树（右）
    }

    // ==================== 中序遍历：左 → 中 → 右 ====================
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result); // 1. 递归遍历左子树（左）
        result.add(root.val); // 2. 访问当前节点（中）
        inorder(root.right, result); // 3. 递归遍历右子树（右）
    }

    // ==================== 后序遍历：左 → 右 → 中 ====================
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }

    private void postorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postorder(root.left, result); // 1. 递归遍历左子树（左）
        postorder(root.right, result); // 2. 递归遍历右子树（右）
        result.add(root.val); // 3. 访问当前节点（中）
    }

}

总结

  • 二叉树递归遍历的核心是确定 “访问根节点” 的时机，前 / 中 / 后序仅调整该步骤的位置；
  • 前序：先根后左右，中序：先左后根再右，后序：先左右后根；
  • 递归终止条件统一为 “节点为空则返回”，是所有递归遍历的基础。