https://leetcode.com/problems/binary-tree-preorder-traversal/

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> lst = new ArrayList<>();
	pre(root, lst);
	return lst;
}
private void pre(TreeNode node, List<Integer> lst) {
	if (node == null) {
		return;
	}
	lst.add(node.val);
	pre(node.left, lst);
	pre(node.right, lst);
}

Iterative solution

Pre-order, in-order, or post-order are all depth-first search (DFS). So, using a stack is clearly the way to go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> list = new ArrayList<>();
	if (root == null) {
		return list;
	}
	Stack<TreeNode> stack = new Stack<>();
	stack.push(root);
	while (!stack.isEmpty()) {
		TreeNode tn = stack.pop();
		list.add(tn.val);
		if (tn.right != null) {
			stack.push(tn.right);
		}
		if (tn.left != null) {
			stack.push(tn.left);
		}
	}
	return list;
}

Cool solution (Divide & Conquer)

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> list = new ArrayList<>();
	if (root == null) {
		return list;
	}
	List<Integer> left = preorderTraversal(root.left);
	List<Integer> right = preorderTraversal(root.right);
	list.add(root.val);
	list.addAll(left);
	list.addAll(right);
	return list;
}