做一视频网站多少钱,公司网络营销的方案思路,重庆做网站哪个好些嘛,杭州网站维护公司代码随想录二刷 #xff5c;二叉树 #xff5c;145.二叉树的后序遍历 题目描述解题思路代码实现递归法迭代法 题目描述
145.二叉树的后序遍历
给你一棵二叉树的根节点 root #xff0c;返回其节点值的 后序遍历 。
示例 1#xff1a; 输入#xff1a;root [1,null,2,… 代码随想录二刷 二叉树 145.二叉树的后序遍历 题目描述解题思路代码实现递归法迭代法 题目描述
145.二叉树的后序遍历
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 1 输入root [1,null,2,3] 输出[3,2,1]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100
进阶递归算法很简单你可以通过迭代算法完成吗
解题思路
代码实现
递归法
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec);traversal(cur-right, vec);vec.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};迭代法
// 后序遍历左右中
// 入栈顺序中右左
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node);st.push(NULL);if (node-right) st.push(node-right);if (node-left) st.push(node-left);} else {st.pop();node st.top();st.pop();result.push_back(node-val);}}return result;}
};
