Binary Tree Preorder Traversal

题目：

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

接口：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in vector which contains node values.
     */
    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here

    }
};

分析：

最基本的二叉树遍历，目前只会用traversal方法实现...用时30秒，一次可以通过

定义节点：

struct TreeNode {
public:
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

解法：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in vector which contains node values.
     */
    void dfs(TreeNode* root, vector<int>& results) {
        if (root == NULL) {
            return;
        }

        results.push_back(root->val);
        dfs(root->left, results);
        dfs(root->right, results);

    } 

    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return vector<int>();
        }
        vector<int> results;
        dfs(root, results);
        return results;
    }
};