前言

二叉树算是比较简单的数据类型，也是常用的数据类型。

二叉树有多种遍历方式，前序、中序、后序、层序遍历。

中序和层序遍历写起来有些不同，记录一下。

前三种遍历都可以借助栈实现迭代遍历，不用递归。

层序遍历则可以借助队列。

前序遍历

遵循 中-左-右 方式输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> preorderTraversal(TreeNode root) {
    if(root == null){
        return new ArrayList<>();
    }
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();

    stack.push(root);

    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        res.add(node.val);
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }

    return res;
}

后序遍历

先讲后序遍历的原因就是只需要更换一下入栈顺序即可

出栈顺序 左-右-中，反转一下就变成 中-右-左

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
public List<Integer> postorderTraversal(TreeNode root) {
    // 左 右 中
    // 反转的 中 右 左
    if(root == null){
        return new ArrayList<>();
    }

    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();

    stack.push(root);

    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        res.add(node.val);
        if(node.left != null){
            stack.push(node.left);
        }

        if(node.right != null){
            stack.push(node.right);
        }
    }

    Collections.reverse(res);
    return res;
}

中序遍历

比较麻烦的是这个，因为 左-中-右 常规思想会重复判断 中 有无左孩子。

因此加个判断条件即可：如果左孩子被访问了，现在回到了父节点，那么不允许再访问左孩子。

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
public List<Integer> inorderTraversal(TreeNode root) {
    // 左中右
    if(root == null) return new ArrayList<>();

    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();

    boolean flag = false;
    stack.push(root);

    while(!stack.isEmpty()){
        TreeNode node = stack.peek();
        if(node.left != null && !flag) { // 没有回退
            stack.push(node.left);
        }
        else{
            stack.pop();
            flag = true; // 访问完毕，回退
            res.add(node.val);
            if(node.right != null) {
                flag = false; // 要进入新的右孩子节点
                stack.push(node.right);
            }
        }
    }

    return res;
}

层序遍历

使用队列保存每层的节点即可，出列前提前记录本层有多少个节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> levelOrder(TreeNode root) {
    if(root == null){
        return new ArrayList<>();
    }
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    queue.offer(root);

    while(!queue.isEmpty()){
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        for(int i = 0; i < levelSize; i++){
            TreeNode node = queue.poll();
            level.add(node.val);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }

    return res;
}