本文主要是介绍2021-10-9 145. 二叉树的后序遍历（递归+迭代），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
注：
题目：
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1\2/3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解：
方法一 ：递归
复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> result;void dfs(TreeNode* node){if(node==nullptr){return ;}dfs(node->left);dfs(node->right);result.push_back(node->val);return ;}vector<int> postorderTraversal(TreeNode* root) {dfs(root);return result;}
};
方法二：迭代
思路与算法
序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root==nullptr){return result;}else{st.push(root);}while(!st.empty()){TreeNode* node=st.top();st.pop();result.push_back(node->val);if(node->left!=nullptr){st.push(node->left); }if(node->right!=nullptr){st.push(node->right);}}reverse(result.begin(),result.end());return result;}
};
这篇关于2021-10-9 145. 二叉树的后序遍历（递归+迭代）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
