二叉树遍历公式汇总

前序遍历

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

中序遍历

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

后序遍历

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

层序遍历

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
 public List<List<Integer>> levelOrder(TreeNode root) {  
        checkFun01(root,0);  
//        checkFun02(root);  
        return resList;  
    }  
    //DFS--递归  
    public void checkFun01(TreeNode node, Integer deep) {  
        if (node == null){  
            return;  
        }        
        deep++;  
        if (resList.size() < deep){  
            ArrayList<Integer> item = new ArrayList<>();  
            resList.add(item);  
        }        
        resList.get(deep-1).add(node.val);  
  
        checkFun01(node.left, deep);  
        checkFun01(node.right,deep);  
    }  
    //BFS--迭代  
    public void checkFun02(TreeNode node) {  
        if (node == null){  
            return;  
        }        
        Queue<TreeNode> que = new LinkedList<>();  
        que.offer(node);  
  
        while (!que.isEmpty()) {  
            ArrayList<Integer> item = new ArrayList<>();  
            int len = que.size();  
  
            while (len > 0){  
                TreeNode tempNode = que.poll();  
                item.add(tempNode.val);  
  
                if (tempNode.left != null) que.offer(tempNode.left);  
                if (tempNode.right != null) que.offer(tempNode.right);  
                len--;  
            }  
            resList.add(item);  
        }    
        }