Binary Tree Inorder Traversal | Leetcode

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

Solution: In-order traversal is to go left first, then take self, then go right. The trick here is to use a stack to simulate recursion. Besides that, we also need a current node that can help us to cleanly process off the nodes that we pop off the stack. Whatever we pop off the stack, we cannot push it back. If we do that we will get into an infinite loop.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                list.add(node.val);
                node = node.right;
            }
        }
        
        return list;
    }
}