题意

给定一个二叉树，返回他的后序遍历的序列。

范围:

节点数不大于100

方法

递归遍历树

按题意所说,通过递归遍历树来获得其后续遍历

每次先遍历左子树,再右子树,最后根

以题目样例为例

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    vector<int> dfs(TreeNode * r){
        if(r == nullptr)return {};
        auto ln = dfs(r->left); // 获取左侧
        auto rn = dfs(r->right); // 获取右侧
        ln.insert(ln.end(),rn.begin(),rn.end()); // 合并左右
        ln.push_back(r->val);
        return ln;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        return dfs(root);
    }
};

复杂度分析

时间复杂度: 对树上每个节点操作次数为常数次,但合并树每次插入是子树节点个数,所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要在记录结果的数组,空间复杂度为$O(n)O(n)$

引用优化合并

如果能降低每次两数组合并的代价,甚至不需要合并就好了

利用C++提供的引用,让所有的输出直接添加到最终的数组里,而不是传给父函数去合并,这样每次直接写在了最终的输出位置

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    void dfs(vector<int>&res,TreeNode * r){ // 递归
        if(r == nullptr)return; // 处理空
        dfs(res,r->left); // 处理左子树
        dfs(res,r->right); // 处理右子树
        res.push_back(r->val); // 处理根
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int> res = {};
        dfs(res,root);
        return res;
    }
};

复杂度分析

时间复杂度: 对树上每个节点操作次数为常数次,所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要在记录结果的数组,空间复杂度为$O(n)O(n)$