94. Binary Tree Inorder Traversal

Link

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?

Solution

Idea:

1. Use stack to record treeNode in order, be sure the last one will be the first traveled

2. push all all root's left node (including it's self) for each node with correct order

3. when a node in stack is handled (i.e, updated to ret), do step 2 for it's right side node

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null||!stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ret.add(root.val);
            root = root.right;
        }
        return ret;
    }
}