-
Notifications
You must be signed in to change notification settings - Fork 1
/
Binary_94.java
161 lines (136 loc) · 4.94 KB
/
Binary_94.java
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
import java.util.*;
public class Binary_94 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// Iterative using a stack (Template can be found in Binary_145)
// Time: O(n)
// Space: O(n)
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while (!stack.empty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val);
p = node.right;
}
/*
while (p != null) {
stack.push(p);
p = p.left;
}
TreeNode node = stack.pop();
result.add(node.val);
p = node.right;
*/
}
return result;
}
// Morris traversal
// Iterative without stack
// Time: O(n)
// Space: O(n)
/*
Step 1: Initialize current as root
Step 2: While current is not NULL,
If current does not have left child
a. Add current’s value
b. Go to the right, i.e., current = current.right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current.left
*/
/*
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
TreeNode left = cur.left;
if (left == null) {
res.add(cur.val);
cur = cur.right; // move to next right node
} else { // has a left subtree
TreeNode pre = left;
while (pre.right != null) { // find rightmost
pre = pre.right;
}
pre.right = cur; // put cur after the pre node
cur.left = null; // original cur left be null, avoid infinite loops
cur = left; // move cur to the top of the new tree
}
}
return res;
}
*/
// Morrise inorder traversal without changing the structure of the tree
/*
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
res.add(current.val);
current = current.right; // move to next right node
} else { // has a left subtree
TreeNode predecessor = current.left;
while (predecessor.right != current && predecessor.right != null) { // find rightmost
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// current needs to be put at the right child of predecessor
predecessor.right = current;
current = current.left;
} else {
// current was previously put at the right child of predecessor
// now we need to unlink them
predecessor.right = null;
res.add(current.val);
current = current.right;
}
}
}
return res;
}
*/
// Assume TreeNode has a parent pointer
// https://www.geeksforgeeks.org/inorder-non-threaded-binary-tree-traversal-without-recursion-or-stack/
/*
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
boolean leftDone = false;
while (root != null) {
// If the left is not traversed, move to the leftmost node
if (!leftDone) {
while (root.left != null)
root = root.left;
}
// This node and its left subtree are all traversed
res.add(root.val);
leftDone = true;
// Now left subtree is all traversed, move to the right subtree or the parent
if (root.right != null) {
root = root.right;
leftDone = false;
} else {
// If this node is the right child of its parent,
// it means the right subtree of its parent is all traversed
// So move to its parent
while (root.parent != null && root == root.parent.right)
root = root.parent;
// If root.parent == null, it means all nodes have been traversed, break the outer loop
// If root.parent != null, move to root.parent
root = root.parent;
}
}
return res;
}
*/
}