⭐算法OJ⭐二叉树的后序遍历【树的遍历】（C++实现）Binary Tree Postorder ...

⭐算法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:

1. Input: root = [1,null,2,3]
2. Output: [3,2,1]

复制代码

Explanation:

Example 2:

1. Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
2. Output: [4,6,7,5,2,9,8,3,1]

复制代码

Explanation:

Example 3:

1. Input: root = []
2. Output: []

复制代码

Example 4:

1. Input: root = [1]
2. Output: [1]

复制代码

1. // 定义二叉树节点
2. struct TreeNode {
3.     int val;
4.     TreeNode* left;
5.     TreeNode* right;
6.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
7. };

复制代码

递归解法

• 后序遍历的次序是：左子树                                         →                                  \rightarrow                     → 右子树                                         →                                  \rightarrow                     → 根节点。
  
• 使用递归实现。
  

1. #include <vector>
2. using namespace std;
4. class Solution {
5. public:
6.     vector<int> postorderTraversal(TreeNode* root) {
7.         vector<int> result; // 存储遍历结果
8.         postorder(root, result); // 递归遍历
9.         return result;
10.     }
12. private:
13.     void postorder(TreeNode* node, vector<int>& result) {
14.         if (node == nullptr) {
15.             return; // 递归终止条件
16.         }
17.         postorder(node->left, result); // 遍历左子树
18.         postorder(node->right, result); // 遍历右子树
19.         result.push_back(node->val); // 访问根节点
20.     }
21. };

复制代码

复杂度分析

• 时间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)，其中                                         n                                  n                     n 是二叉树的节点数。每个节点被访问一次。
  
• 空间复杂度：                                        O                            (                            h                            )                                  O(h)                     O(h)，其中                                         h                                  h                     h 是二叉树的高度。递归调用栈的深度取决于树的高度。
  

迭代解法（使用栈）

• 使用 栈 模仿递归过程。
  
• 每次从栈中弹出一个节点，将其值插入效果列表的开头。
  
• 先压入左子树，再压入右子树，以确保右子树先被处理。从根节点开始，先将所有左子节点入栈，然后访问节点，再转向右子树。
  

1. #include <vector>
2. #include <stack>
3. using namespace std;
5. class Solution {
6. public:
7.     vector<int> postorderTraversal(TreeNode* root) {
8.         vector<int> result;
9.         if (root == nullptr) {
10.             return result;
11.         }
12.         stack<TreeNode*> stk;
13.         stk.push(root);
14.         while (!stk.empty()) {
15.             TreeNode* node = stk.top();
16.             stk.pop();
17.             result.insert(result.begin(), node->val); // 将节点值插入结果的开头
18.             if (node->left) {
19.                 stk.push(node->left); // 先压入左子树
20.             }
21.             if (node->right) {
22.                 stk.push(node->right); // 再压入右子树
23.             }
24.         }
25.         return result;
26.     }
27. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。