首页 > 其他 > 详细

Binary Tree Postorder Traversal ***

时间:2015-07-27 18:33:47      阅读:193      评论:0      收藏:0      [点我收藏+]

Given a binary tree, return the postorder traversal of its nodes‘ values.

For example:
Given binary tree {1,#,2,3},

   1
         2
    /
   3

 

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

 

Analyse: root->left, root->right, root.

1. Recursion

    Runtime: 0ms.

 1 /**
 2  * Definition for a binary tree node.
 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         if(!root) return result;
15         
16         postorder(root, result);
17         return result;
18     }
19     void postorder(TreeNode* root, vector<int>& result){
20         if(root->left) postorder(root->left, result);
21         if(root->right) postorder(root->right, result);
22         result.push_back(root->val);
23     }
24 };

 

2. Iteration: Only when the children of the parent are visited or the parent has no children, this parent can be pushed into the vector as visited. Otherwise, we should push its right child and left child respectively. See reference from Binary Tree Postorder Traversal

    Runtime: 0ms.

 1 /**
 2  * Definition for a binary tree node.
 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         if(!root) return result;
15         stack<TreeNode* >stk;
16         stk.push(root);
17         TreeNode* visited = root;
18         
19         while(!stk.empty()){
20             root = stk.top();
21             
22             if(root->right == visited || root->left == visited || (!root->left) && (!root->right)){
23                 result.push_back(root->val);
24                 stk.pop();
25                 visited = root;
26             }
27             else{
28                 if(root->right) stk.push(root->right);
29                 if(root->left) stk.push(root->left);
30             }
31         }
32         return result;
33     }
34 };

 

Binary Tree Postorder Traversal ***

原文:http://www.cnblogs.com/amazingzoe/p/4680453.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!