binary tree preorder travelsal

binary tree preorder travelsal

easy problem

Basic skills. Recursive way is easy. Iterative way is not hard too. DFS and push the value to the result when visiting a point at the first time.

Recursive way.

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode *root) {
13         vector < int > result;
14         result.clear();
15         preOrder(root,result);
16         return result;
17     }
18     void preOrder( TreeNode* root, vector < int >& result ) {
19         if ( !root ) {
20             return;
21         }
22         result.push_back(root->val);
23         preOrder(root->left,result);
24         preOrder(root->right,result);
25     }
26 };

Iterative way

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode *root) {
13         vector < int > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         stack < TreeNode* > S;
19         while( !S.empty() ) {
20             S.pop();
21         }
22         S.push(root);
23         while( !S.empty() ) {
24             TreeNode* p = S.top();
25             S.pop();
26             result.push_back(p->val);
27             if ( p->right ) {
28                 S.push(p->right);
29             }
30             if ( p->left ) {
31                 S.push(p->left);
32             }
33         }
34         return result;
35     }
36 };

Loading Disqus comments...
Table of Contents