-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0114.java
More file actions
130 lines (120 loc) · 4.13 KB
/
Copy pathSolution0114.java
File metadata and controls
130 lines (120 loc) · 4.13 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
// 114. 二叉树展开为链表
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/*
* 迭代思路：
* 1、简单理解：把左子树塞到根节点和右节点中间，每个节点都要做同样的操作
* 2、简单情况分析：
* 1）根节点为空：直接返回列表
* 2）只有根节点：将根节点的值存入列表，返回列表
* 3）有根节点和左节点：将左节点移到右节点的位置，遍历右节点将值存入列表，返回列表
* 4）有根节点和右节点：不用移动，遍历右节点将值存入列表，返回列表
* 5）有根节点、左节点、右节点：将左节点移到根节点和右节点中间，遍历右节点将值存入列表，返回列表
* 3、节点连接步骤：
* 1）前序遍历是中左右，即根节点→左子树→右子树
* 2）左子树遍历的最后一个节点是 左子树的最后一个右子节点，因此要将其连接到根节点的右节点上
* 3）根节点的右指针要指向左节点，左指针指向空，从而形成中左右的链表
* 4、遍历逻辑：
* 1）根指针的移动代表着前序遍历的顺序，循环遍历条件是根指针不为空
* 2）如果根节点的左节点不为空，则进行节点连接步骤；如果为空，则将节点值存入列表
* 3）根节点处理完后，根指针指向右节点，准备下一轮判断
* 5、“144.二叉树的前序遍历”展开为链表的解法
* */
class Solution {
public List<Integer> flatten(TreeNode root) {
List<Integer> list = new ArrayList<>();
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
list.add(root.val);
root = root.right;
}
return list;
}
}
/*
* 迭代思路：与上个解法相同。用队列/栈存储下一个要遍历的节点，替代了遍历指针，缺点是使用了多余的空间
* */
class Solution {
public List<Integer> flatten(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
list.add(root.val);
if (root.right != null) {
queue.offer(root.right);
}
}
return list;
}
}
// 方法返回空写法。迭代
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
}
// 递归
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
flatten(root.left);
flatten(root.right);
}
}