剑指 Offer 第 32 题-从上到下打印二叉树
描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
数据范围： 节点数量 0≤n≤1000 ，节点上的值满足 1≤val≤10^5，保证节点上的值各不相同
要求：空间复杂度 O(n) ，时间时间复杂度 O(n^2)
提示：
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
4.参考下面的二叉搜索树，示例 1
方法 1
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
|
public class Jz32 {
public static void main(String[] args) {
final Jz32 jz = new Jz32();
final TreeNode root = new TreeNode(8);
final TreeNode node10 = new TreeNode(10);
root.left = new TreeNode(6);
root.right = node10;
node10.left = new TreeNode(1);
node10.right = new TreeNode(2);
System.out.println(jz.PrintFromTopToBottom(root));
}
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
final ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
final TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
|
扩展-按层次打印
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
| package algorithm.jzoffer;
import java.util.LinkedList;
import java.util.Queue;
public class Jz32_3 {
public static void main(String[] args) {
final Jz32_3 jz = new Jz32_3();
final TreeNode root = new TreeNode(8);
final TreeNode node10 = new TreeNode(10);
final TreeNode node6 = new TreeNode(6);
root.left = node6;
root.right = node10;
node10.left = new TreeNode(1);
node10.right = new TreeNode(2);
node6.left = new TreeNode(7);
node6.right = new TreeNode(11);
jz.PrintFromTopToBottom(root);
}
public void PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int toBePrint = 1;
int nextLevel = 0;
while (!queue.isEmpty()) {
final TreeNode node = queue.poll();
System.out.printf("%s\t", node.val);
if (node.left != null) {
queue.offer(node.left);
nextLevel++;
}
if (node.right != null) {
queue.offer(node.right);
nextLevel++;
}
toBePrint--;
if (toBePrint == 0) {
System.out.println();
toBePrint = nextLevel;
nextLevel = 0;
}
}
}
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
|
扩展-按「之」字打印
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| package algorithm.jzoffer;
import java.util.Stack;
public class Jz32_4 {
public static void main(String[] args) {
final Jz32_4 jz = new Jz32_4();
final TreeNode node1 = new TreeNode(1);
final TreeNode node2 = new TreeNode(2);
final TreeNode node3 = new TreeNode(3);
final TreeNode node4 = new TreeNode(4);
final TreeNode node5 = new TreeNode(5);
final TreeNode node6 = new TreeNode(6);
final TreeNode node7 = new TreeNode(7);
final TreeNode node8 = new TreeNode(8);
final TreeNode node9 = new TreeNode(9);
final TreeNode node10 = new TreeNode(10);
final TreeNode node11 = new TreeNode(11);
final TreeNode node12 = new TreeNode(12);
final TreeNode node13 = new TreeNode(13);
final TreeNode node14 = new TreeNode(14);
final TreeNode node15 = new TreeNode(15);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node4.left = node8;
node4.right = node9;
node5.left = node10;
node5.right = node11;
node6.left = node12;
node6.right = node13;
node7.left = node14;
node7.right = node15;
jz.PrintFromTopToBottom(node1);
}
public void PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty() || !stack2.isEmpty()) {
while (!stack1.isEmpty()) {
final TreeNode node = stack1.pop();
System.out.printf("%s\t", node.val);
if (node.left != null) {
stack2.push(node.left);
}
if (node.right != null) {
stack2.push(node.right);
}
}
System.out.println();
while (!stack2.isEmpty()) {
final TreeNode node = stack2.pop();
System.out.printf("%s\t", node.val);
if (node.right != null) {
stack1.push(node.right);
}
if (node.left != null) {
stack1.push(node.left);
}
}
System.out.println();
}
}
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
|