# leetcode解題：(Easy) 144. Binary Tree Preorder Traversal

題目：[https://leetcode.com/problems/binary-tree-preorder-traversal/](https://leetcode.com/problems/binary-tree-preorder-traversal/)

描述：給定一棵二元樹(Binary tree)的根(root)，回傳整棵樹按前序遍歷(Preorder traversal)取出的值

解題思路：二元樹遍歷常見解法不是用Stack就是用遞迴(這邊用遞迴)，按前序遍歷的順序：中(父節點)->左子節點->右子節點把值塞進List裡就行了
*註：在看其他解法時還有發現Morris traversal法，時間複雜度與Stack、遞迴一樣為O(n)，空間複雜度則為O(1)，之後再來試試*

程式碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> result = new ArrayList<Integer>();

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

    public void preorder(TreeNode node) {
        if(node == null) return;
        result.add(node.val);
        preorder(node.left);
        preorder(node.right);
    }
}

時間複雜度：O(n)
空間複雜度：遞迴本身為O(h)，需要額外空間儲存答案則是O(n)

###### tags: `leetcode` `easy` `binary tree` `DFS`