设二叉树共有 $n$ 个结点，函数 preorderTraversal 以下代码的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

1struct TreeNode {2   int val;3   TreeNode* left;4   TreeNode* right;5   TreeNode(int x): val(x), left(nullptr), right(nullptr) {}6};7 8void preorder(TreeNode *root, vector<int> &res) {9   if (root == nullptr) {10      return;11   }12   res.push_back(root->val);13   preorder(root->left, res);14   preorder(root->right, res);15}16 17vector<int> preorderTraversal(TreeNode *root) {18   vector<int> res;19   preorder(root, res);20   return res;21};