前言：复习并总结树的遍历方式
树节点
1
2
3
4
5
6
7
8
9
| class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}
|
先序遍历
递归
1
2
3
4
5
6
7
| public void preorderTraversal(TreeNode root) {
if (root != null) {
System.out.println(root.getValue());
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
|
while循环
建立辅助栈，先输出当前结点，然后将右结点、左结点依次放入栈，然后根据栈先入后出的特性，会先输出左结点再输出右结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode root = stack.pop();
System.out.println(root.getValue());
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
}
|
中序遍历
递归
1
2
3
4
5
6
7
| public void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.println(root.getValue());
inorderTraversal(root.right);
}
}
|
while循环
建立辅助栈，将结点依次放入栈直到最左端，然后输出当前结点并赋值右结点
1
2
3
4
5
6
7
8
9
10
11
12
| public void inorderTraversal(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<>();
while (root != null || ! stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
System.out.println(root.getValue());
root = root.right;
}
}
|
后序遍历
递归
1
2
3
4
5
6
7
| public void postorderTraversal(TreeNode root){
if(root != null){
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.println(root.getValue());
}
}
|
while循环
建立两个辅助栈，将结点按根右左的顺序放入reverseData中，最后遍历reverseData即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public void postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<TreeNode> reverseData = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
reverseData.push(root);
if (root.left != null) {
stack.push(root.left);
}
if (root.right != null) {
stack.push(root.right);
}
}
while (!reverseData.isEmpty()) {
TreeNode node = reverseData.pop();
System.out.println(node.value);
}
}
|
层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void bfs(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
System.out.println(root.value);
if (root.left != null) {
queue.push(root.left);
}
if (root.right != null) {
queue.push(root.right);
}
}
}
|