Inorder traversal

public class Solution{
	class TreeNode{
		int val;
		TreeNode left, right;
		public TreeNode(int val){
			this.val = val;
			this.left = null;
			this.right = null;
		}
	}



	/*
		left son -> father->right son

	*/

	//non-recursion
	public List<Integer> inOrderTraversal(TreeNode root){
		Stack<Integer> stack = new Stack<>();
		List<Integer> res = new ArrayList<>();

		
		TreeNode cur = root;
		while(cur != null || !stack.isEmpty()){
			//add 左侧树到
			while(cur != null ){
				stack.push(cur);
				cur = cur.left;
			}

			cur = stack.pop();
			res.add(cur.val);
			cur = cur.right;

		}

		return res;
	}
}