C++，递归

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class Solution {15 public:16     /**17      * @param root: The root of binary tree.18      * @return: Preorder in vector which contains node values.19      */20     vector
     
       preorderTraversal(TreeNode *root) {21         // write your code here22         vector
      
        result;23         if (root == NULL) {24             return result;25         }26         result.insert(result.end(), root->val);27         if (root->left != NULL) {28             vector
       
         left = preorderTraversal(root->left);29             result.reserve(result.size()+left.size());30             result.insert(result.end(), left.begin(), left.end());31         }32         if (root->right != NULL) {33             vector
        
          right = preorderTraversal(root->right);34             result.reserve(result.size()+right.size());35             result.insert(result.end(), right.begin(), right.end());36         }37         return result;38     }39 };
        
       
      
     

C++，递归，辅助函数

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class Solution {15 public:16     /**17      * @param root: The root of binary tree.18      * @return: Preorder in vector which contains node values.19      */20     vector
     
       preorderTraversal(TreeNode *root) {21         // write your code here22         vector
      
        result;23         if (root == NULL) {24             return result;25         } else {26             preorderCore(root, result);27         }28         return result;29     }30     void preorderCore(TreeNode *root, vector
       
         &result) {31         if (root == NULL) {32             return ;33         }34         result.insert(result.end(), root->val);35         if (root->left != NULL) {36             preorderCore(root->left, result);37         }38         if (root->right != NULL) {39             preorderCore(root->right, result);40         }41     }42 };
       
      
     

 C++，非递归

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class Solution {15 public:16     /**17      * @param root: The root of binary tree.18      * @return: Preorder in vector which contains node values.19      */20     vector
     
       preorderTraversal(TreeNode *root) {21         // write your code here22         vector
      
        result;23         if (root == NULL) {24             return result;25         }26         stack
       
         sta;27         TreeNode *cur = root;28         while (cur!=NULL || !sta.empty()) {29             while (cur != NULL) {30                 result.insert(result.end(), cur->val);31                 sta.push(cur);32                 cur = cur->left;33             }34             cur = sta.top();35             sta.pop();36             cur = cur->right;37         }38         return result;39     }40 };