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

注：

题目：
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]

   1
    
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解：
方法一 ：递归
复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

class Solution {
public:
    vector result;
    void dfs(TreeNode* node){
        if(node==nullptr){
            return ;
        }
        dfs(node->left);
        dfs(node->right);
        result.push_back(node->val);
        return ;
    }
    vector postorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
};

方法二：迭代
思路与算法
序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector result;
        stack 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;
    }
};