题意

把二叉搜索数改为累加树

限制:

节点数不大于$10^{4}10^4$

方法

从大到小找节点并加和

因为原树是二叉搜索树,所以节点大小关系为左<根<右

现在题目要求把每个节点的值,变为比原树中更大节点之和.因此按照, 右->根->左的顺序遍历按大到小找出节点,

最后进行加和即可

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> ns = {};
    void dfs(TreeNode * root){
        if(root == nullptr)return ;
        dfs(root -> right); // 右侧 节点
        ns.push_back(root); // 放入根节点
        dfs(root -> left); // 左侧 节点
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    TreeNode* convertBST(TreeNode* root) {
        ns = {};
        dfs(root); // 获取从大到小的顺序
        for(int i = 1;i<ns.size();i++){ // 进行累加
            ns[i]->val += ns[i-1]->val;
        }
        return root;
    }
};

复杂度分析

时间复杂度: 每个节点处理复杂度为常数代价,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 空间复杂度主要消耗在递归和记录从大到小的节点上,所以空间复杂度为$O(n)O(n)$

从大到小递归并加和

注意到C++可以使用引用或指针来让不同层级的递归都访问同一个值,这里如果能共享到当前最大加和,就不需要处理完以后再进行加和,而可以一边递归一边加和了.

以题目样例数据{1,0,2}为例

因此三次加和根节点,也就写入了三次根节点的值,所以输出为{3,3,2}

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode * dfs(TreeNode * root, int & s){
        if(root == nullptr)return root;
        dfs(root -> right, s); // 右侧 节点
        root -> val = s = root->val + s; // 加上比它大的所有数的和
        dfs(root -> left, s); // 左侧 节点
        return root;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    TreeNode* convertBST(TreeNode* root) {
        int s = 0; // 当前更大的值的和
        return dfs(root, s);
    }
};

复杂度分析

时间复杂度: 每个节点处理复杂度为常数代价,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 空间复杂度主要消耗在递归上,所以空间复杂度为$O(n)O(n)$