> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/66binary-tree-preorder-traversal.md).

# 66.Binary Tree Preorder Traversal

## 1.Description(Easy)

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

**Example**

Given:

```
    1
   / \
  2   3
 / \
4   5
```

return`[1,2,4,5,3]`.

[**Challenge**](https://www.lintcode.com/en/problem/binary-tree-preorder-traversal/#challenge)

Can you do it without recursion?

## 2.Code

Recurision: Divided Conquer && Traversal

Non-recursion:Stack

Divided Conquer:

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

        List<Integer> left=preorderTraversal(root.left);
        List<Integer> right=preorderTraversal(root.right);

        result.add(root.val);
        result.addAll(left);
        result.addAll(right);

        return result;
    }
```

Traversal:

```
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Helper(result,root);
        return result;
    }

    public void Helper(List<Integer> result,TreeNode root){
        if(root==null){
            return;
        }
        result.add(root.val);
        Helper(result,root.left);
        Helper(result,root.right);
    }
```

Non-recursive:

由于stack的特性，先压root, 再压root.right,再压root.left

```
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();

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

        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode current=stack.pop();
            result.add(current.val);
            if(current.right!=null){
                stack.push(current.right);
            }
            if(current.left!=null){
                stack.push(current.left);
            }
        }
        return result;
    }
```