二叉树

# 二叉树

提示

草稿

# 二叉树概念

# 二叉树遍历

前序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后续遍历：左 -> 右 -> 根

# 前序遍历

递归

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    dfs(list, root.left);
    dfs(list, root.right);
}

1
2
3
4
5
6

迭代

public void preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            System.out.print(root.val + " ");
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        root = root.right;
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 中序遍历

递归

public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    dfs(list, root.left);
    System.out.print(root.val + " ");
    dfs(list, root.right);
}

1
2
3
4
5
6

迭代

public void inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        System.out.print(root.val + " ");
        root = root.right;
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 后续遍历

递归

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    dfs(list, root.left);
    dfs(list, root.right);
    System.out.print(root.val + " ");
}

1
2
3
4
5
6

迭代

public void postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();

    TreeNode prev = null;
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (root.right == null || root.right == prev) {
            System.out.print(root.val + " ");
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

编辑

上次更新: 2024/05/12, 22:10:12

← 背包问题红黑树→