# 0144. Binary Tree Preorder Traversal
###### tags: `Leetcode` `Easy` `Preorder Traversal`
Link: https://leetcode.com/problems/binary-tree-preorder-traversal/

## Code
### Recursion

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        if(root==null)return l;
        traversal(root,l);
        return l;
    }
    public void traversal(TreeNode root, List<Integer> l){
        l.add(root.val);
        if(root.left!=null) traversal(root.left,l);
        if(root.right!=null) traversal(root.right,l);
    }
}

### 颜色标记法

class Solution {
    class ColorNode{
        TreeNode node;
        int color;
        public ColorNode(TreeNode node, int color){
            this.node = node;
            this.color = color;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        if(root==null)return l;
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root,0));
        while(!stack.isEmpty()){
            ColorNode cn = stack.pop();
            if(cn.color == 0){
                if(cn.node.right!=null) stack.push(new ColorNode(cn.node.right,0));
                if(cn.node.left!=null) stack.push(new ColorNode(cn.node.left,0));
                stack.push(new ColorNode(cn.node,1));
            }
            else{
                l.add(cn.node.val);
            }
        }
        return l;
    }
}

### Morris

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        // if(root==null)return l;
        TreeNode predecessor;
        while(root!=null){
            if(root.left==null){
                l.add(root.val);
                root = root.right;
            }
            else{
                predecessor = root.left;
                while(predecessor.right!=null && predecessor.right!=root){
                    predecessor = predecessor.right;
                }
                if(predecessor.right==null){
                    l.add(root.val);
                    predecessor.right = root;
                    root = root.left;
                }
                else{
                    predecessor.right = null;
                    root = root.right;
                }
            }
        }
        return l;
    }
}