⭐算法OJ⭐二叉树的后序遍历【树的遍历】（C++实现）Binary Tree Postorder Traversal
⭐算法OJ⭐二叉树的中序遍历【树的遍历】（C++实现）Binary Tree Inorder Traversal⭐算法OJ⭐二叉树的前序遍历【树的遍历】（C++实现）Binary Tree Preorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Example 1:
Input: root =
Output:
Explanation:
https://i-blog.csdnimg.cn/direct/70c11042b40a4b0eae8ec6bb61a9905c.png
Example 2:
Input: root =
Output:
Explanation:
https://i-blog.csdnimg.cn/direct/2dec865e58b846398920be39f5747b19.png
Example 3:
Input: root = []
Output: []
Example 4:
Input: root =
Output:
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
递归解法
[*]后序遍历的次序是：左子树 → \rightarrow → 右子树 → \rightarrow → 根节点。
[*]使用递归实现。
#include <vector>
using namespace std;
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result; // 存储遍历结果
postorder(root, result); // 递归遍历
return result;
}
private:
void postorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return; // 递归终止条件
}
postorder(node->left, result); // 遍历左子树
postorder(node->right, result); // 遍历右子树
result.push_back(node->val); // 访问根节点
}
};
复杂度分析
[*]时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉树的节点数。每个节点被访问一次。
[*]空间复杂度： O ( h ) O(h) O(h)，其中 h h h 是二叉树的高度。递归调用栈的深度取决于树的高度。
迭代解法（使用栈）
[*]使用 栈 模仿递归过程。
[*]每次从栈中弹出一个节点，将其值插入效果列表的开头。
[*]先压入左子树，再压入右子树，以确保右子树先被处理。从根节点开始，先将所有左子节点入栈，然后访问节点，再转向右子树。
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) {
return result;
}
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
result.insert(result.begin(), node->val); // 将节点值插入结果的开头
if (node->left) {
stk.push(node->left); // 先压入左子树
}
if (node->right) {
stk.push(node->right); // 再压入右子树
}
}
return result;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]