2021-10-9 145. 二叉树的后序遍历（递归+迭代）

本文主要是介绍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;}
};