94 Binary Tree Inorder Traversal
94. Binary Tree Inorder Traversal
1. Question
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree[1,null,2,3]
,
1
\
2
/
3
return[1,3,2]
.
Note: Recursive solution is trivial, could you do it iteratively?
2. Implementation
(1) Morris Tree Traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
TreeNode curNode = root, preNode = null;
while (curNode != null) {
if (curNode.left == null) {
res.add(curNode.val);
curNode = curNode.right;
}
else {
preNode = curNode.left;
while (preNode.right != null && preNode.right != curNode) {
preNode = preNode.right;
}
if (preNode.right == null) {
preNode.right = curNode;
curNode = curNode.left;
}
else {
res.add(curNode.val);
preNode.right = null;
curNode = curNode.right;
}
}
}
return res;
}
}
(2) Iteration
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
// Method 1: Iterative Stack
TreeNode curNode = root;
Stack<TreeNode> stack = new Stack<>();
while (curNode != null || !stack.isEmpty()) {
if (curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
else {
curNode = stack.pop();
res.add(curNode.val);
curNode = curNode.right;
}
}
return res;
}
}
3. Time & Space Complexity
(1) Morris Tree Traversal: 时间复杂度: O(n), 空间复杂度: O(1)
(2) Iteration: 时间复杂度: O(n), 空间复杂度:O(h)
Last updated
Was this helpful?