Binary Tree Preorder Traversal

Java

//stack 
class Solution {
		public List<Integer> preorderTraversal(TreeNode root) {
				List<Integer> result = new ArrayList<>();
				LinkedList<TreeNode> stack = new LinkedList<>();
				
				if (root == null) return result;
				stack.push(root);
				while (!stack.isEmpty()) {
					TreeNode node = stack.pop();
					result.add(node.val);        //add result before children 
					if (node.right != null) {
						stack.push(node.right);
					}
					if (node.left != null) {
						stack.push(node.left); //后加进去，希望它先出来
					}
				}
				return result;
		}
}

//recursion 
class Solution {
		public List<Integer> preorderTraversal(TreeNode root) {
			
			List<Integer> result = new ArrayList<>();
		if (root == null) return result;
		
			result.add(root.val);
			List<Integer> left = preorderTraversal(root.left);
			List<Integer> right = preorderTraversal(root.right);
			
			result.addAll(left);
			result.addAll(right);
			return result;
		}
}


//use helper function 
class Solution {
		public List<Integer> preorderTraversal(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; //base case 
			
			result.add(root.val);
			helper(root.left, result);
			helper(root.right, result);
		}
}