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].
解题思路：
递归版：
class Solution {
public:
void getpostOrderData(TreeNode* root, vector<int> &ret)
{
if(!root) return;
if(root->left) getpostOrderData(root->left,ret);
if(root->right) getpostOrderData(root->right,ret);
ret.push_back(root->val);
return;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
getpostOrderData(root,ret);
return ret;
}
};
迭代版：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> stk;
TreeNode* curr = root;
TreeNode* last = NULL;
while(curr || !stk.empty())
{
while(curr)
{
stk.push(curr);
curr = curr->left;
}
TreeNode* temp = stk.top();
if(temp->right && last != temp->right )
curr = temp->right;
else{
ret.push_back(temp->val);
last = temp;
stk.pop();
}
}
return ret;
}
};
