preorder Traversal

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



	/*
		father->left son->right son

	*/

		//recursion
	public List<Integer> preorderTraversal(TreeNode root){
		List<Integer> res = new ArrayList<>();
		traversal(res,root);
		return res;

	}

	public void traversal(List<Integer> res, TreeNode root){
		if (root == null) {
			return res;
		}

		res.add(root.val);
		traversal(res,root.left);
		traversal(res,root.right);

	}
	//non-recursion
	public List<Integer> preorderTraversal(TreeNode root){
		Stack<Integer> stack = new Stack<>();
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		stack.push(root);

		while(!stack.isEmpty()){
			TreeNode node = stack.pop();
			res.add(node.val);
			
			//be careful, add right node before left node
			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}

		return res;
	}
}