二叉树遍历和深度问题

二叉树遍历包括前序,中序,以及后序遍历,主要有两种解法:递归,深度优先的非递归算法。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
import java.util.Stack;

/*
* 1
* / \
* 2 3
* / /
* 4 5
* / \
* 6 7
* \
* 8
*
* 遍历此二叉树,并求最大深度
*/


class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

public class BinaryTreeDepth {
public static void main(String...args){
TreeNode root = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
root.left = n2;
root.right = n3;
n2.left = n4;
n3.left = n5;
n4.left = n6;
n4.right = n7;
n6.right = n8;


System.out.print("递归前序:");
preorderTraversal(root);
System.out.print(" 非递归前序:");
preorderTraversal_NoRecursive(root);

System.out.print("\n递归中序:");
inorderTraversal(root);
System.out.print(" 非递归中序:");
inorderTraversal_NoRecursive(root);

System.out.print("\n递归后序:");
postorderTraversal(root);
System.out.print(" 非递归后序:");
postorderTraversal_NoRecursive(root);

System.out.print("\n递归求二叉树的最大深度:" + maxDepth(root));
System.out.println(" 非递归求二叉树的最大深度:" + maxDepthDFS(root));
}



/******************遍历问题**********************/
//递归的前序遍历
public static void preorderTraversal(TreeNode root) {
if(root == null) return;
System.out.print(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
//递归的中序遍历
public static void inorderTraversal(TreeNode root) {
if(root == null) return;
inorderTraversal(root.left);
System.out.print(root.val);
inorderTraversal(root.right);
}
//递归的后序遍历
public static void postorderTraversal(TreeNode root) {
if(root == null) return;
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val);
}

//非递归的前序遍历,深度优先,用栈
public static void preorderTraversal_NoRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null) return;
//首先把左子树都压栈,边压栈边读,得到最后一个左节点,将其删除,再将其的右节点作为新的root压栈。
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
System.out.print(root.val);
root = root.left;
}
root = stack.pop();
root = root.right;
}
}

//非递归的中序遍历
public static void inorderTraversal_NoRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null) return;
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
System.out.print(root.val);
root = root.right;
}
}

//非递归的后序遍历,需要标记右子树是否被访问过
public static void postorderTraversal_NoRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<Integer> stag = new Stack<Integer>();//标记对应的节点的右节点是否已经被访问了
if(root == null) return;
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
stag.push(0);
root = root.left;
}
if(stag.peek() == 1){
//如果此右节点被访问过,或者其没有右节点,那么此时可以读这个节点
System.out.print(stack.pop().val);
stag.pop();
root = null;
}else{
root = stack.peek();
root = root.right;
stag.pop();
stag.push(1);
}
}
}






/******************最大深度问题**********************/

//递归求最大深度
public static int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
return left < right ? right : left;
}

//深度优先搜索求最大深度,利用了后序遍历,每次输出的时候计算栈的大小
public static int maxDepthDFS(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<Integer> stag = new Stack<Integer>();//标记右子树是否被访问过
int treeDeep = 0;
while(root != null || !stack.isEmpty()){
//把左子树压栈
while(root != null){
stack.push(root);
stag.push(0);
root = root.left;
}

if(stag.peek() == 1){//如果该节点的右子树被访问过了
treeDeep = Math.max(treeDeep, stack.size());
stack.pop();
stag.pop();
root = null;
}else{
root = stack.peek();
root = root.right;
stag.pop();
stag.push(1);//节点的右子树被访问过了,标记置为1
}
}
return treeDeep;
}

}