二叉树如何遍历 递归算法遍历 迭代算法遍历

发表于

递归算法遍历

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
scss复制代码/**
     * 前序遍历
     */
    public static int[] preTraversalTree(TreeNode rootNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        preOrder(rootNode, arrayList);
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 前序遍历
     */
    public static void preOrder(TreeNode rootNode, ArrayList<Integer> list) {
        if (rootNode == null) {
            return;
        }
        list.add(rootNode.val);
        preOrder(rootNode.left, list);
        preOrder(rootNode.right, list);
    }

    /**
     * 中序遍历
     *
     * @param rootNode
     * @param list
     */
    public static int[] inTraversalTree(TreeNode rootNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        inOrder(rootNode, arrayList);
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 中序遍历
     *
     * @param rootNode
     * @param list
     */
    public static void inOrder(TreeNode rootNode, ArrayList<Integer> list) {
        if (rootNode == null) {
            return;
        }
        inOrder(rootNode.left, list);
        list.add(rootNode.val);
        inOrder(rootNode.right, list);
    }

    /**
     * 后序遍历
     *
     * @param rootNode
     */
    public static int[] postTraversalTree(TreeNode rootNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        postOrder(rootNode, arrayList);
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 后序遍历
     *
     * @param rootNode
     * @param list
     */
    public static void postOrder(TreeNode rootNode, ArrayList<Integer> list) {
        if (rootNode == null) {
            return;
        }
        postOrder(rootNode.left, list);
        postOrder(rootNode.right, list);
        list.add(rootNode.val);
    }

迭代算法遍历

前序遍历

思路与算法

我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

Image.png

Image [2].png、

Image [3].png

Image [4].png

Image [5].png

Image [7].png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ini复制代码public static List<Integer> preOrderTraverse(TreeNode rootNode) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (rootNode != null || !stack.isEmpty()) {
            while (rootNode != null) {
                arrayList.add(rootNode.val);
                stack.push(rootNode);
                rootNode = rootNode.left;
            }
            TreeNode pop = stack.pop();
            rootNode = pop.right;
        }
        return arrayList;
    }

后序遍历

Image [8].png

Image [9].png

Image [10].png

Image [11].png

Image [12].png

Image [13].png

Image [14].png

Image [15].png

Image [16].png

Image [17].png

Image [18].png

Image [19].png

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
ini复制代码public static List<Integer> postOrderTraverse(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
ini复制代码Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            arrayList.add(root.val);
            root = root.right;
        }
        return arrayList;

【参考】

【1】leetcode

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%