使用了两种方法对二叉树进行后序遍历,具体可以参考二叉树相关知识点总结。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; postorder2(root,result); return result; } private: void postorder1(TreeNode* root, vector<int>& result){ if(root==nullptr) return; postorder1(root->left,result); postorder1(root->right,result); result.push_back(root->val); } void postorder2(TreeNode* root, vector<int>& result){ if(root==nullptr) return; stack<TreeNode*> s; stack<int> res; s.push(root); TreeNode* n; while(!s.empty()){ n=s.top(); s.pop(); res.push(n->val); if(n->left) s.push(n->left); if(n->right) s.push(n->right); } while(!res.empty()){ int t=res.top(); res.pop(); result.push_back(t); } } };
|