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