剑指 Offer 32 - II. 从上到下打印二叉树 II

Posted on | In
Words count in article: 425 | Reading time ≈ 2

题目

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
例如:
给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
   
   返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

提示：

  • 节点总数 <= 1000

解法

解法一：

JAVA

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
public List<List<Integer>> levelOrder(TreeNode root) {
        if (Objects.isNull(root)) {
            return Collections.emptyList();
        }

        Queue<TreeNode> nodes = new ArrayDeque<>();
        nodes.add(root);

        List<List<Integer>> result = new ArrayList<>();

        while (!nodes.isEmpty()) {
            Queue<TreeNode> tempQueue = new ArrayDeque<>();
            List<Integer> temp = new ArrayList<>();
            while (!nodes.isEmpty()) {
                TreeNode node = nodes.poll();
                temp.add(node.val);
                if (!Objects.isNull(node.left)) {
                    tempQueue.add(node.left);
                }

                if (!Objects.isNull(node.right)) {
                    tempQueue.add(node.right);
                }
            }
            nodes = tempQueue;
            result.add(temp);
        }
        return result;
    }

解法二：

超时

Java

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
public int[] spiralOrder(int[][] matrix) {

        if (Objects.isNull(matrix)) {
            return null;
        }
        
        if (0 == matrix.length) {
            return new int[]{};
        }

        int[][] directions = new int[4][2];
        directions[0] = new int[]{0, 1};     // x++;
        directions[1] = new int[]{1, 0};     // y++;
        directions[2] = new int[]{0, -1};     // x--;
        directions[3] = new int[]{-1, 0};     // y--

        int[] result = new int[matrix.length * matrix[0].length];
        int index = 0;
        Set<String> visited = new HashSet<>(result.length);
        int row = matrix.length;
        int col = matrix[0].length;
        int directionIndex = 0;
        int r = 0;
        int c = 0;
        while (index < result.length) {
            String p = r + "_" + c;
            if (visited.contains(p)) {
                continue;
            }

            result[index++] = matrix[r][c];

            if (directionIndex == 0 && (c + 1) == col) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 1 && (r + 1) == row) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 2 && (c == 0 || visited.contains(p))) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 3 && (r == 0 || visited.contains((r - 1) + "_" + c))) {
                // 转向
                directionIndex = 0;
            }
            r += directions[directionIndex][0];
            c += directions[directionIndex][1];
            visited.add(p);
        }
        return result;
    }
0%