NC45 实现二叉树先序，中序和后序遍历

描述
给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围：0≤n≤1000，树上每个节点的val值满足0≤val≤100
要求：空间复杂度 O(n)，时间复杂度 O(n)
样例解释：

示例1
输入：{1,2,3}
返回值：[[1,2,3],[2,1,3],[2,3,1]]
说明：
如题面图  

示例2
输入：{}
返回值：[[],[],[]]

备注：n≤10^6
1
2
3
4
5
6
7
8
9
10
11

牛客网
递归思路：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int [][]result = new int[3][];
        result[0] = frontPrint(root);
        result[1] = middlePrint(root);
        result[2] = endPrint(root);
        return result;
    }
    ArrayList<Integer> front = new ArrayList<>();
    ArrayList<Integer> middle = new ArrayList<>();
    ArrayList<Integer> end = new ArrayList<>();
    public int[] frontPrint(TreeNode root) {
        TreeNode node = root;
        if (root == null) return new int[0];
        front.add(root.val);
        frontPrint(root.left);
        frontPrint(root.right);
        return front.stream().mapToInt(Integer::intValue).toArray();
    }
    public int[] middlePrint(TreeNode root) {
        TreeNode node = root;
        if (root == null) return new int[0];
        middlePrint(root.left);
        middle.add(root.val);
        middlePrint(root.right);
        return middle.stream().mapToInt(Integer::intValue).toArray();
    }
    public int[] endPrint(TreeNode root) {
        TreeNode node = root;
        if (root == null) return new int[0];
        endPrint(root.left);
        endPrint(root.right);
        end.add(root.val);
        return end.stream().mapToInt(Integer::intValue).toArray();
    }
}
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

迭代方式：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int [][]result = new int[3][];
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return new int[3][0];
        TreeNode front = root;
        stack.add(front);
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null)
                stack.add(node.right);
            if (node.left != null)
                stack.add(node.left);
        }
        result[0] = list.stream().mapToInt(Integer::intValue).toArray();
        // 中
        TreeNode middle = root;
        list = new ArrayList<>();
        while (!stack.isEmpty() || middle != null) {
            if (middle != null) {
                stack.push(middle);
                middle = middle.left;
            } else {
                middle = stack.pop();
                list.add(middle.val);
                middle = middle.right;
            }
        }
        result[1] = list.stream().mapToInt(Integer::intValue).toArray();
        TreeNode end = root;
        list = new ArrayList<>();
        while (!stack.isEmpty() || end != null) {
            if (end != null) {
                stack.push(end);
                list.add(0,end.val);
                end = end.right;
            } else {
                end = stack.pop();
                end = end.left;
            }

        }
        result[2] = list.stream().mapToInt(Integer::intValue).toArray();
        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
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