Binary Tree Inorder Traversal

Java

//stack
class Solution {
		public List<Integer> inorderTraversal(TreeNode root) {
			List<Integer> result = new ArrayList<>();
			LinkedList<TreeNode> stack = new LinkedList<>();
			
			TreeNode cur = root;
			while (cur != null || !stack.isEmpty()) {
				while (cur != null) {
					stack.push(cur);
					cur = cur.left;
				}
				cur = stack.pop();    //先把最左边的TreeNode pop出来加入result
				result.add(cur.val);
				cur = cur.right;  //若cur.right 为空，就会再继续执行两行前，再对cur赋值
			}
			return result; 
		}
}


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