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?

>
read more on how binary tree is serialized on OJ.

思路：二叉树的中序遍历，是典型的递归算法。可是题目中建议非递归实现。所以还是有些思考的。

只是算是基础题。感觉是必须掌握的。

代码例如以下（递归实现）：

/**

 * 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> list = new ArrayList<Integer>();

    public List<Integer> inorderTraversal(TreeNode root) {

    	/**

    	 * 中序遍历，先左子树，再根，最后右子树

    	 */

        if(root == null)

            return list;

        if(root.left != null){

            inorderTraversal(root.left);

        }

        list.add(root.val);

        if(root.right != null){

            inorderTraversal(root.right);

        }

        return list;

    }

}

非递归实现：

/**

 * 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<Integer> inorderTraversal(TreeNode root) {

    	/**

    	 * 非递归实现中序遍历

    	 * 中序遍历，先左子树，再根。最后右子树

    	 */

    	List<Integer> list = new ArrayList<Integer>();

    	if(root == null)

    		return list;

    	TreeNode p = root;

    	Stack<TreeNode> st = new Stack<>();

    	while(p != null || !st.isEmpty()){

    		if(p != null){

    			st.push(p);

    			p = p.left;

    		}else{

    			p = st.pop();

    			list.add(p.val);

    			p = p.right;

    		}

    	}

        return list;

    }

}