将二叉搜索树改为累加树

C++ 解法, 执行用时: 6ms, 内存消耗: 1292KB, 提交时间: 2021-12-11

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    TreeNode* convertBST(TreeNode* root) {
        if(nullptr==root) return 0;
        convertBST(root->right);
        root->val+=sum;
        sum=root->val;
        convertBST(root->left);
        return root;
    }
    
private:
    int sum=0;
};

C++ 解法, 执行用时: 6ms, 内存消耗: 1328KB, 提交时间: 2022-02-08

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /*
    题意整理
    1. 给定一个二叉搜索树，树上的节点各不相同。
    2. 现在要将其修改为累加树，使每个节点的值变成原树中更大节点之和。
    
    方法一：递归
    
    解题思路
    由于二叉搜索树的左子树节点值总是小于当前节点，右子树节点值总是大于当前节点。
    所以按右、根、左顺序遍历时，树中的节点值一定是从大到小变化的，
    只要在遍历的过程中记录当前累加和，即可得到当前节点即将被替换的值。
    
    */
    TreeNode* convertBST(TreeNode* root) {
        //特殊情况判断
        if(root == NULL) return root;
        //遍历整棵树
        dfs(root);
        return root;
    }
    
private:
    //记录当前累加和
    int sum=0;
     
    //按右、根、左顺序遍历整棵树
    void dfs(TreeNode* root) {
        //递归结束条件
        if(root == NULL) return;
        //遍历右子树
        dfs(root->right);
        //更新累加和
        sum += root->val;
        //更新当前节点值为累加和sum
        root->val = sum;
        //遍历左子树
        dfs(root->left);
    }
    
};

C++ 解法, 执行用时: 6ms, 内存消耗: 1420KB, 提交时间: 2021-11-27

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    int sum = 0;

    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1304KB, 提交时间: 2022-06-29

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    //递归
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }
    int sum=0;
    void traverse(TreeNode* root){
        if(root==NULL) return ;
        //逆中序，从右开始，因为右子总是大的
        traverse(root->right);
        sum+=root->val;
        root->val=sum;
        traverse(root->left);
    }
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1324KB, 提交时间: 2022-01-24

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    int pre = 0;
    TreeNode* convertBST(TreeNode* root) {
        // write code here
        traversal(root);
        return root;
    }
    void traversal(TreeNode* root){
        if(root == NULL) return;
        traversal(root->right);
        root->val += pre;
        pre = root->val;
        traversal(root->left);
    }
};

详情