二叉树的先序、中序、后序、层序遍历（递归&非递归）

一、先序遍历

递归

    /**
     * 前序遍历，根左右。
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preTraversal(root, result);
        return result;
    }

    private void preTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preTraversal(root.left, result);
        preTraversal(root.right, result);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

非递归

 /**
     * 前序遍历，根左右。
     * 栈
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        stack.add(root);
        while (!stack.isEmpty()) {
            //当栈不为空
            root = stack.pop();
            result.add(root.val);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return result;
    }

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

二、中序遍历

递归

 /**
     * 中序遍历 递归
     * 左中右
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        inTraversal(root, result);
        return result;
    }

    private void inTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inTraversal(root.left, result);
        result.add(root.val);
        inTraversal(root.right, result);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

非递归

   /**
     * 中序遍历  栈
     * 左中右
     * 中序遍历不用提前添加结点
     * 判断时需要判断当前结点是否为空
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                root = stack.pop();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、后序遍历

递归

 /**
     * 后序遍历，左右根
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        postTraversal(root, result);
        return result;
    }

    private void postTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postTraversal(root.left, result);
        postTraversal(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

非递归

 /**
     * 后序遍历，左右根
     * 栈
     *
     * @param root
     * @return
     */
    public List<Integer> postTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<>();
        //根右左，然后逆序遍历，和先序差不多
        stack.add(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            result.add(root.val);
            if (root.left != null) {
                stack.add(root.left);
            }
            if (root.right != null) {
                stack.add(root.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

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

当然，不借助工具类，也可以用栈接收一下。

  /**
     * 后序遍历
     * @param head
     */
    public static void postTraversal2(Node head) {
        //中 右 左遍历，然后逆序
        if (head == null) {
            return;
        }
        Stack<Node> reverse = new Stack<Node>();
        Stack<Node> stack = new Stack<Node>();
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            reverse.push(head);

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

        while (!reverse.isEmpty()) {
            System.out.println(reverse.pop().value+" ");
        }
    }
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 static void postTraversal3(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        stack.push(head);
        Node node = null;
        while (!stack.isEmpty()) {
            //查看当前结点
            node = stack.peek();
            if (node.left != null && head != node.left && head != node.right) {
            //如果有左子结点，并且左右子结点未被遍历  则加入
                stack.push(node);
            } else if (node.right != null && head != node.right) {
                //如果有右节点，并且右子节点未被遍历 则加入
                stack.push(node);
            } else {
                System.out.println(stack.pop());
                //如果是叶子结点，或者左右已经遍历过了，则弹出，标记遍历过的结点
                head = node;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四、层序遍历

递归

  /**
     * 层序遍历 递归
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        //里面的list是每层的元素
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        checkFun01(root, 0, result);
        return result;
    }

    private void checkFun01(TreeNode root, int deep, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        //深度增加
        deep++;
        if (result.size() < deep) {
            //如果出现了新的一层
            result.add(new ArrayList<>());
        }
        //本层元素加入本层列表
        result.get(deep - 1).add(root.val);
        checkFun01(root.left, deep, result);
        checkFun01(root.right, deep, result);
    }
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

非递归

    /**
     * 层序遍历，队列
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Deque<TreeNode> deque = new ArrayDeque();
        if (root == null) {
            return result;
        }
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> level = new ArrayList<>();
            while (size > 0) {
                root = deque.poll();
                level.add(root.val);
                if (root.left != null) {
                    deque.offer(root.left);
                }
                if (root.right != null) {
                    deque.offer(root.right);
                }
                size--;
            }
            result.add(level);
        }
        return result;
    }

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