网站开发与维护好找工作吗,比wordpress还好,社区推广活动方案,在线制作图表文章目录1. 题目信息2. 解法2.1 递归2.2 循环#xff0c;必须掌握a. 单栈b. 双栈解法3. 前中后序总结1. 题目信息
给定一个二叉树#xff0c;返回它的 后序 遍历。
示例:输入: [1,null,2,3] 1\2/3 输出: [3,2,1]进阶: 递归算法很简单#xff0c;你可以通过迭代算法完成吗…
文章目录1. 题目信息2. 解法2.1 递归2.2 循环必须掌握a. 单栈b. 双栈解法3. 前中后序总结1. 题目信息
给定一个二叉树返回它的 后序 遍历。
示例:输入: [1,null,2,3] 1\2/3 输出: [3,2,1]进阶: 递归算法很简单你可以通过迭代算法完成吗
来源力扣LeetCode 链接https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解法
2.1 递归 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;preorder(root, ans);return ans;}void preorder(TreeNode* root, vectorint ans){if(root NULL)return;preorder(root-left, ans);preorder(root-right, ans);ans.push_back(root-val);}
};2.2 循环必须掌握
左右根
a. 单栈
先按照根-右-左的顺序遍历二叉树(和先序遍历有些像)然后将遍历的结果反转过来就是“左-右-根”也就是后序遍历了
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;stackTreeNode* stk;while(root || !stk.empty()){while(root){stk.push(root);ans.push_back(root-val);root root-right;}root stk.top()-left;stk.pop();}//反转遍历结果reverse(ans.begin(),ans.end());return ans;}
};以下解法会破坏二叉树
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;if(rootNULL)return ans;TreeNode *cur;stackTreeNode* stk;stk.push(root);while(!stk.empty()){cur stk.top();if(cur-left){stk.push(cur-left);cur-left NULL;}else if(cur-right){stk.push(cur-right);cur-right NULL;}else{ans.push_back(cur-val);stk.pop();}}return ans;}
};b. 双栈解法 stk1模仿前序遍历的实现“反后序遍历”stk2保存stk1的pop元素
class Solution {
public:vectorint postorderTraversal(TreeNode *root) {vectorint ans;if(root NULL) return ans;stackTreeNode* stk1;stackTreeNode* stk2;stk1.push(root);TreeNode *cur;while(!stk1.empty()){cur stk1.top();stk1.pop();stk2.push(cur);if(cur-left)stk1.push(cur-left);if(cur-right)stk1.push(cur-right);}while(!stk2.empty()){cur stk2.top();stk2.pop();ans.push_back(cur-val);}return ans;}
};3. 前中后序总结
