LeetCode #145

# Description:

## Example:

``````Note
``````

# Code:

Iteration version

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode *p, *q;

stack<TreeNode *> stack_node;
p=root;

do{
while(p != NULL){  /* 往左下走 */
stack_node.push(p);
p = p->left;
}
q=NULL;
while(!stack_node.empty()){
p=stack_node.top();
stack_node.pop();
if(p->right==q){ /* 右孩子不存在或已被访问，访问之 */
result.push_back(p->val);
q=p;  /* 保存刚访问过的结点 */
}
else{ /* 当前结点不能访问，需第二次进栈 */
stack_node.push(p);
p=p->right; /* 先处理右子树 */
break;
}
}
} while(!stack_node.empty());

return result;

}

};
``````

Recursion version

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;

RecursionPostorder(root, result);
return result;
}

void RecursionPostorder(TreeNode* root, vector<int> &result){
if(root==NULL) return;

RecursionPostorder(root->left, result);
RecursionPostorder(root->right, result);
result.push_back(root->val);
}
};
``````