binary tree postorder travelsal

binary tree postorder travelsal

Normal problem

Easy to user recursive way to resolve this. Iterat solution is not very hard to figure out.

Recurisive one

 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> postorderTraversal(TreeNode *root) {
13         vector< int > result;
14         result.clear();
15         travel(root,result);
16         return result;
17     }
18     void travel( TreeNode* root, vector< int > &result ) {
19         if ( !root ) {
20             return;
21         }
22         travel(root->left,result);
23         travel(root->right,result);
24         result.push_back(root->val);
25     }
26 };

Iterative solition

Postorder travelsal is something like DFS, and when we get back to the point we already visited before we put it into the result. Using a stack to save the path.Each time we get the top of the stack. If this is the second time we visit it, and we just put it to the back of result. If this is the first time we visited it, just put it back and push it's left and right child into the stack if there is left or right child.

 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> postorderTraversal(TreeNode *root) {
13         vector< int > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         stack < pair< TreeNode*, int > > S;
19         while( !S.empty() ) {
20             S.pop();
21         }
22         S.push(pair < TreeNode*, int > (root, 0));
23         while( !S.empty() ) {
24             auto p = S.top();
25             S.pop();
26             if ( p.second == 1 ) {
27                 result.push_back(p.first->val);
28             } else {
29                 S.push(pair < TreeNode*, int > (p.first,1));
30                 if ( p.first->right ) {
31                     S.push(pair < TreeNode*, int > (p.first->right,0));
32                 }
33                 if ( p.first->left ) {
34                     S.push(pair < TreeNode*, int > (p.first->left,0));
35                 }
36             }
37         }
38         return result;
39     }
40 };

Loading Disqus comments...
Table of Contents