[Leetcode] 94. Binary Tree Inorder Traversal explained
![title image](/public/images/leetcode-teaser.png)
Problem
94. Binary Tree Inorder Traversal
Approach
Recursive approach is trivial.
We can implement inorder traversal using Stack
.
curNode <- root
while true:
if curNode is null:
if stack is empty:
break;
tmpNode <- stack.pop();
add tmpNode.val to result
curNode <- tmpNode.right;
else:
if curNode is not null:
push curNode into stack
else:
curNode <- curNode.left;
Code
Recursive approach
/**
* author: jooncco
* written: 2022. 9. 8. Tue. 11:34:14 [UTC+9]
**/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
inorder(result, root);
return result;
}
private void inorder(List<Integer> arr, TreeNode node) {
if (node == null) return;
inorder(arr, node.left);
arr.add(node.val);
inorder(arr, node.right);
}
}
Iterative approach
/**
* author: jooncco
* written: 2022. 9. 8. Tue. 13:36:14 [UTC+9]
**/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result= new LinkedList<>();
TreeNode curNode = root;
while (true) {
if (curNode == null) {
if (stack.isEmpty()) break;
result.add(stack.peek().val);
curNode= stack.pop().right;
} else {
if (curNode.left != null) {
stack.push(curNode);
curNode= curNode.left;
} else {
result.add(curNode.val);
curNode= curNode.right;
}
}
}
return result;
}
}
Complexity
- Time: \(O(n)\)
- Space: \(O(n)\)
Leave a comment