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?

confused what "{1,#,2,3}" means? 

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    //第一个是非递归解法：    //借助栈数据结构，将最左侧的节点入栈，到达最左侧节点时，弹出栈顶，填入结果，然后遍历栈顶的右节点    //第二种是递归，比较简单   /* public List
     
       inorderTraversal(TreeNode root) {        List
      
        res=new ArrayList
       
        ();        Stack
        
          stack=new Stack
         
          ();        TreeNode node=root;        while(!stack.empty()||node!=null){            while(node!=null){                                stack.push(node);                node=node.left;            }            node=stack.pop();            res.add(node.val);            node=node.right;        }        return res;    }*/    List
          
            res=new ArrayList
           
            (); public List
            
              inorderTraversal(TreeNode root) { getInorder(root); return res; } public void getInorder(TreeNode root){ if(root==null) return; inorderTraversal(root.left); res.add(root.val); inorderTraversal(root.right); }}