Binary Tree Inorder Traversal (LeetCode HashMap)

Question: 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].

Idea: The problem can be solved by recursion. Visit left node, then append current value, finally visit right node. The code of the iteration method is also provided.

Time: O(n)  Space: O(n)

Recursive Code:

 public class Solution {  
   public List<Integer> inorderTraversal(TreeNode root) {  
     List<Integer> result=new ArrayList<Integer>();  
     dfs(root,result);  
     return result;  
   }  
   public void dfs(TreeNode root,List<Integer> result)  
   {  
     if(root==null)  
     {  
       return;  
     }  
     dfs(root.left,result);  
     result.add(root.val);  
     dfs(root.right,result);  
   }  
 }  

Iterative Code:

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