原题链接：Leetcode 144. Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3] Output: [1,2,3]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
方法一：递归 思路：
二叉树的三个遍历都可以方便的用递归实现，只需要改变访问根结点、访问左孩子、访问右孩子的次序即可
c++代码：
class Solution {
public:
vector ans;
vector preorderTraversal(TreeNode* root) {
// 为空则直接返回
if(root == NULL)
return ans;
ans.emplace_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return ans;
}
};
复杂度分析：
- 时间复杂度：O(n)，需要遍历每个结点
- 空间复杂度：O(n)，最坏情况下，递归栈的深度是整个树所有结点之和
