-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTreeMorrisDisplay.java
More file actions
138 lines (123 loc) · 4.74 KB
/
TreeMorrisDisplay.java
File metadata and controls
138 lines (123 loc) · 4.74 KB
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
package algorithmUtils;
import lombok.Data;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* *********************************************************************
* <br/>
*1. 如果当前节点的左子节点为空时，输出当前节点，并将当前节点置为该节点的右子节点；
2. 如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；
2.1. 如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，当前节点置为其左子节点；
2.2. 如果最右节点的右指针不为空，将最右节点右指针重新置为空(恢复树的原状)，输出当前节点，并将当前节点置为其右节点；
3. 重复1~2，直到当前节点为空。
---------------------
*/
public class TreeMorrisDisplay {
/**
* 左右两边分成2份 左边遍历完通过父节点回调到右节点 如果没有子树直接打印
* @when 2019/3/27
*/
public static void main(String[] args) {
/**
* 4
* 2 6
* 1 3 5 7
*
* @when 2019/3/27
*/
TreeNode head = new TreeNode(4);
head.left = new TreeNode(2);
head.right = new TreeNode(6);
head.left.left = new TreeNode(1);
head.left.right = new TreeNode(3);
head.right.left = new TreeNode(5);
head.right.right = new TreeNode(7);
System.out.println(Arrays.toString(Morris_InOrder(head).toArray()));
}
public static List<Integer> Morris_InOrder(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
if(root == null) {
/**
* 返回空
* @when 2019/3/27
*/
return resultList;
}
/**
* 当前指针currentNode指向 当前节点
* 前驱指针prevNode 指向前一个节点
* @when 2019/3/27
*/
TreeNode currentNode = root;
TreeNode prevNode =null;
/**
* 当前指针不为空
* @when 2019/3/27
*/
while(currentNode != null) {
/**
* 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
* @when 2019/3/27
*/
if(currentNode.left == null) {
resultList.add(currentNode.val);
currentNode = currentNode.right;
}
/**
* 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
* @when 2019/3/27
*/
else {
/**
* 前驱节点指针：循环找到当前节点左子树下最右边的节点
* @when 2019/3/27
*/
prevNode = currentNode.left;
/**
* 前驱节点右节点不等于当前节点
*/
while(prevNode.right != null && prevNode.right != currentNode){
prevNode = prevNode.right;
}
if(prevNode.right == null) {
/**
* 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
* @when 2019/3/27
*/
prevNode.right = currentNode;
currentNode = currentNode.left;
}
else {
/**
* 这种情况是父节点为当前节点 左子树的right为父节点 =》相等 ：pre节点已经跟父节点连接好
* 此时父节点左子树已经遍历完
* 打印父节点 并下一步开始遍历右子树
* @when 2019/3/27
*/
/**
* 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子
* @when 2019/3/27
*/
resultList.add(currentNode.val);
prevNode.right = null;
currentNode = currentNode.right;
}
}
}
/**
* 重复直到当前节点为空
* @when 2019/3/27
*/
return resultList;
}
@Data
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}