https://oj.leetcode.com/problems/binary-tree-inorder-traversal/

http://blog.csdn.net/linhuanmars/article/details/20187257

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) 
    {
        // Solution A:
        // return inorderTraversal_Recursion(root);
        
        // Solution B:
        // return inorderTraversal_StackA(root);
        
        // Solution C:
        // return inorderTraversal_StackB(root);
        
        // Solution D:
        return inorderTraversal_NoExtraSpace(root);
    }

    /////////////////////
    // Solution D: No Extra Space
    // See http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
    // 
    // Use last pre.right -> cur
    public List<Integer> inorderTraversal_NoExtraSpace(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();
        
        TreeNode cur = root;
        TreeNode pre = null;
        
        while (cur != null)
        {
            if (cur.left == null)
            {
                result.add(cur.val);
                cur = cur.right;
            }
            else
            {
                // Find pre of cur in inorder traversal
                // which is the most right child in cur‘s left sub tree
                pre = cur.left;
                while (pre.right != null && pre.right != cur)
                    pre = pre.right;
                    
                if (pre.right == null)
                {
                    // Mark theLastOne.right -> currentMySelf
                    pre.right = cur;
                    cur = cur.left;
                }
                else  
                {
                    // All left been visited.
                    pre.right = null;  
                    result.add(cur.val);  
                    cur = cur.right;  
                }
            }
        }
        
        return result;
    }


    /////////////////////
    // Solution C: Stack B
    //    
    public List<Integer> inorderTraversal_StackB(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty())
        {
            if (root != null)
            {
                stack.push(root);
                root = root.left;
            }
            else
            {
                root = stack.pop();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }

    /////////////////////
    // Solution B: Stack A
    //
    public List<Integer> inorderTraversal_StackA(TreeNode root)
    {
        List<Integer> result = new ArrayList<>();
        
        if (root == null)
            return result;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.empty())
        {
            TreeNode node = stack.peek(); // Note!! not pop

            if (node.left != null)
            {
                stack.push(node.left);
                continue;
            }
            
            node = stack.pop();
            result.add(node.val);
            
            if (node.right != null)
                stack.push(node.right);
        }
        
        return result;
    }

    /////////////////////
    // Solution A: Recursion
    //
    public List<Integer> inorderTraversal_Recursion(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        visit(root, order);
        return order;
    }
    
    private void visit(TreeNode node, List<Integer> order)
    {
        if (node == null)
            return;

        visit(node.left, order);
        order.add(node.val);
        visit(node.right, order);
    }
}

[LeetCode]94 Binary Tree Inorder Traversal