Question

link

   1
    \
     2
    /
   3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a classic AND EXTREMELY IMPORTANT question.

Solution is well explained in this blog:

First, the current pointer is initialized to the root. Keep traversing to its left child while pushing visited nodes onto the stack. When you reach a NULL node (ie, you’ve reached a leaf node), you would pop off an element from the stack and set it to current. Now is the time to print current’s value. Then, current is set to its right child and repeat the process again. When the stack is empty, this means you’re done printing.

Code

concise code, hard to think of

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    while (p != null || ! stack.isEmpty()) {
        if (p != null) {
            stack.push(p);
            p = p.left;
        }
        else if (! stack.isEmpty()) {
            TreeNode temp = stack.pop();
            ans.add(temp.val);
            p = temp.right;
        }
    }
    return ans;
}

more intuitive code, written by Oct 8th, 2014

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<Integer>();
    if (root == null) {
        return ans;
    }

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    while (p != null) {
        stack.push(p);
        p = p.left;
    }
    while (!stack.isEmpty()) {
        p = stack.pop();
        ans.add(p.val);
        p = p.right;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
    return ans;
}