# Preorder

## ้ข็ฎๆ่ฟฐ

``````Given a binary tree, return the preorder traversal of its nodes' values.

The first data is the root node, followed by the value of the left and right son nodes, and "#" indicates that there is no child node.
The number of nodes does not exceed 20.``````

## ไปฃ็ 

### Approach #1 No-Recursion

``````public class Solution {
public List<Integer> preorderTraverl(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<IInteger> preorder = new ArrayList<Interger>();

if (root == null) {
return preorder;
}

stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}

return preorder;
}

}``````

### Approach #2 Traverse

``````class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
traverse(root, result);
return results;
}

private void traverse(TreeNode root, ArrayList<Integer> result) {
if (root == null) return;

travese(root.left, result);
travese(root.right, result);
}
}``````

### Approach #3 Divide & Conquer

``````class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null) return result;

// Divide
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);

// Conquer