二叉树的遍历

发表于 | 分类于

二叉树的遍历方法有两大类、4 种方法

  • DFS
    • PreOrder
    • InOrder
    • PostOrder
  • BFS

前序遍历、中序遍历和后序遍历都是深度优先遍历的方法，不同在于根节点的遍历顺序不同

前序遍历：先输出根节点，再前序遍历左子树，最后遍历右子树
中序遍历：先中序遍历左子树，再输出跟节点，最后中序遍历右子树
后序遍历：先后序遍历左子树，接着后序遍历右子树，最后输出根节点

前序遍历：A -> B -> C
中序遍历：B -> A -> C
后序遍历：B -> C -> A

一张从 LeetCode 上拿来的图，数字表示节点的遍历顺序

代码实现

用递归来写是最简单的了，没什么好讲的

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
/**
 * 前序遍历
 */
public void PreOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    System.out.println(root.val);
    PreOrder(root.left);
    PreOrder(root.right);
}

/**
 * 中序遍历
 */
public void InOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    InOrder(root.left);
    System.out.println(root.val);    
    InOrder(root.right);
}

/**
 * 后序遍历
 */
public void PostOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    
    PostOrder(root.left);
    PostOrder(root.right);
    System.out.println(root.val);
}

144. Binary Tree Preorder Traversal
938. Range Sum of BST
589. N-ary Tree Preorder Traversal