LeetCode538把二叉搜索树转换为累加树-创新互联

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

通过上图题目给出的例子可以看出，8节点修改后的值还是8，7节点修改之后是15(7+8)，6节点修改之后是21(6+15)，以此类推。所以可以876543210的顺序遍历，每遍历一个节点都将值改为当前节点与下一个节点的值相加。

中序遍历为012345678

所以，应以中序遍历逆序的方式遍历，将代码左中右改为右中左即可满足需求。再定义一个指向上一个节点的指针。

class Solution {
public:
    TreeNode* pre = nullptr;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return nullptr;
        convertBST(root ->right);
        if(pre) root ->val += pre ->val;
        pre = root;
        convertBST(root ->left);
        return root;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧