94. Binary Tree Inorder Traversal (Medium)
https://leetcode.com/problems/binary-tree-inorder-traversal/
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solutions
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode tmp = root;
while (tmp != null || !stack.isEmpty()) {
// keep all the left nodes into the stack
while (tmp != null) {
stack.push(tmp);
tmp = tmp.left;
}
tmp = stack.pop();
// visit the element value after pop
ans.add(tmp.val);
// find a valid right node to traverse its left nodes
while (!stack.isEmpty() && tmp.right == null) {
tmp = stack.pop();
// visit the element value after pop
ans.add(tmp.val);
}
// reach here, stack empty or tmp.right != null
tmp = tmp.right;
}
return ans;
}
}