[LeetCode] Binary Tree Inorder Traversal

Problem:

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?

Solution:O(n)

public class Solution {
 public class Solution {
    public  ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if(root==null) 
            return ret;
            
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur = root;
        while(!s.isEmpty()||cur!=null){
            if(cur!=null){
                s.push(cur); 
                cur=cur.left;
            }else{
                cur=s.pop();
                ret.add(cur.val);
                cur=cur.right;
            }
        }
        return ret;
    }
}

Key Concept: Using stack and access left as possible