-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathLeetCode_00094.java
More file actions
69 lines (63 loc) · 1.89 KB
/
LeetCode_00094.java
File metadata and controls
69 lines (63 loc) · 1.89 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
package com.github.jerring.leetcode;
import java.util.ArrayList;
import java.util.List;
public class LeetCode_00094 {
// // 递归
// public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> res = new ArrayList<>();
// inorderHelper(root, res);
// return res;
// }
//
// private void inorderHelper(TreeNode root, List<Integer> list) {
// if (root == null) {
// return;
// }
// inorderHelper(root.left, list);
// list.add(root.val);
// inorderHelper(root.right, list);
// }
// // 迭代
// public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> res = new ArrayList<>();
// Stack<TreeNode> stack = new Stack<>();
// while (!stack.isEmpty() || root != null) {
// while (root != null) {
// stack.push(root);
// root = root.left;
// }
// root = stack.pop();
// res.add(root.val);
// root = root.right;
// }
// return res;
// }
// Morris 遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
while (root != null) {
if (root.left == null) {
res.add(root.val);
root = root.right;
} else {
TreeNode pre = getPredecessor(root);
if (pre.right == null) {
pre.right = root;
root = root.left;
} else {
res.add(root.val);
pre.right = null;
root = root.right;
}
}
}
return res;
}
private TreeNode getPredecessor(TreeNode root) {
TreeNode p = root.left;
while (p.right != null && p.right != root) {
p = p.right;
}
return p;
}
}