1 class Solution { 2 public: 3 vector<int> postorderTraversal(TreeNode* root) { 4 stack<TreeNode*> s; 5 vector<int> ans; 6 TreeNode* temp=root; 7 TreeNode* pre=nullptr; 8 while(!s.empty() || temp){ 9 while(temp){ 10 s.push(temp); 11 temp=temp->left; 12 } 13 temp=s.top(); 14 s.pop(); 15 if(temp->right==nullptr || temp->right==pre){ 16 ans.push_back(temp->val); 17 pre=temp; 18 temp=nullptr; 19 } 20 else{ 21 s.push(temp); 22 temp=temp->right; 23 } 24 } 25 return ans; 26 } 27 };
1 class Solution { 2 public: 3 void addPath(vector<int>& ans,TreeNode* root){ 4 TreeNode* temp=root; 5 int count=0; 6 while(temp){ 7 ans.push_back(temp->val); 8 temp=temp->right; 9 count++; 10 } 11 reverse(ans.end()-count,ans.end()); 12 } 13 vector<int> postorderTraversal(TreeNode* root) { 14 vector<int> ans; 15 TreeNode* p=root; 16 TreeNode* q=nullptr; 17 while(p){ 18 if(p->left){ 19 q=p->left; 20 while(q->right && q->right!=p){ 21 q=q->right; 22 } 23 if(q->right==p){ 24 q->right=nullptr; 25 addPath(ans,p->left); 26 p=p->right; 27 } 28 else if(q->right==nullptr){ 29 q->right=p; 30 p=p->left; 31 } 32 } 33 else{ 34 p=p->right; 35 } 36 } 37 addPath(ans,root); 38 return ans; 39 } 40 };
原文:https://www.cnblogs.com/zouma/p/13939041.html