Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [,null,,]
\
/
Output: [,,]
Follow up: Recursive solution is trivial, could you do it iteratively?
方法一：利用两个栈s1,s2来实现，先将头结点入栈s1，从s1弹出栈顶节点记为cur，压入s2中，分别将cur的左右孩子压入s1，当s1为空后，s2的弹出节点次序就是后序遍历的次序。（C++）
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s1,s2;
s1.push(root);
vector<int> res={};
if(!root)
return res;
TreeNode* cur;
while(!s1.empty()){
cur=s1.top();
s1.pop();
s2.push(cur);
if(cur->left)
s1.push(cur->left);
if(cur->right)
s1.push(cur->right);
}
while(!s2.empty()){
cur=s2.top();
s2.pop();
res.push_back(cur->val);
}
return res;
}
方法二：先将头结点压入栈，怎样判断是该结点是应该输入vector中还是应该处理他的孩子？
1.该节点左右孩子为空时，为叶子结点，则该次遍历是输入到vector中
2.上一次输入的结点为该节点右孩子时，说明该结点的子树处理完毕，这次遍历是输入vector中
3.如果上一次输入的结点为该节点的左孩子，且右孩子为空，则该结点处理完毕，这次遍历就是输入vector中
4.否则说明子树没有被访问，按右、左孩子入栈。（C++）
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res={};
if(!root)
return res;
s.push(root);
TreeNode* last=NULL;
TreeNode* top;
while(!s.empty()){
top=s.top();
if((top->left==NULL&&top->right==NULL)||(top->right==NULL&&last==top->left)||(last==top->right&&last!=NULL)){
res.push_back(top->val);
last=top;
s.pop();
}
else{
if(top->right)
s.push(top->right);
if(top->left)
s.push(top->left);
}
}
return res;
}
注意此时要加上这个判定条件，若不加，输出的为2,1，没有把3这个结点入栈
方法三：递归方法（C++）
void postOrder(TreeNode* root,vector<int> &res){
if(!root)
return;
postOrder(root->left,res);
postOrder(root->right,res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res={};
if(!root)
return res;
postOrder(root,res);
return res;
}