94. Binary Tree Inorder Traversal
Problem
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example
Input: root = [1,null,2,3]
Output: [1,3,2]
[1] Code (20. 12. 20)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ansList = new ArrayList<>();
search(root, ansList);
return ansList;
}
private void search(TreeNode treeNode, List<Integer> ansList) {
if (treeNode == null) {
return;
}
search(treeNode.left, ansList);
ansList.add(treeNode.val);
search(treeNode.right, ansList);
}
}
-
Inorder니까 left -> middle -> right 로 순회를 하면 된다.
그런데 문제 조건 중에 Recursive가 아닌 Iterative하게 풀기를 원했다.
Recursive solution is trivial, could you do it iteratively?
[2] Code (20. 12. 20)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
TreeNode curr = root;
List<Integer> ansList = new LinkedList<>();
while (curr != null || s.size() > 0) {
while (curr != null) {
s.push(curr);
curr = curr.left;
}
curr = s.pop();
ansList.add(curr.val);
curr = curr.right;
}
return ansList;
}
}
- Iterative 하게 Inorder Search를 하는 코드이다.
[3] Code (21. 07. 31)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root != null) {
inOrder(ans, root);
}
return ans;
}
public void inOrder(List<Integer> ans, TreeNode node) {
if (node.left != null) {
inOrder(ans, node.left);
}
ans.add(node.val);
if (node.right != null) {
inOrder(ans, node.right);
}
}
}
-
다시 문제를 풀었는데 똑같이 Recursive 하게 풀었다.
아무래도 Recursive가 익숙하다 보니 자연스레 손이 가는 듯하다.
-
그리고 Iterative하게 푸는 코드를 보는데
참 신선한 아이디어이구나를 또(?) 생각했다.
다음엔 이 아이디어가 먼저 떠오를 수 있길 !