/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public List<Integer> inorderTraversal(TreeNode root) {

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

if(root == null) return res;

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

TreeNode cur = root;

while(cur!=null || !stack.empty()){

while(cur!=null){

stack.push(cur);//把root 保存起来临时在stack里面，left先出在出root.

cur = cur.left;

}

cur = stack.pop();

res.add(cur.val);

cur = cur.right;

}

return res;

}

public List<Integer> inorderTraversal(TreeNode root) {

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

if(root == null) return res;

helper(root, res);

return res;

}

private void helper(TreeNode root, List<Integer> res){

if(root == null) return;

helper(root.left,res);

res.add(root.val);

helper(root.right,res);

}

}