leetcode538. Convert BST to Greater Tree

https://www.cnblogs.com/grandyang/p/6591526.html

这个题本质上是中序遍历的反向。中序遍历是从小到大，而这个题目是从大到小，然后每个数加上比自己大的所有数的和。

因为实际上并没有改变树的结构，只是改变了原来树中节点的值，所以用void做返回值就可以了。

每次加sum实际上就是加的所有比当前节点大的数的和，并且这个和一定等于前一个节点的更新值。

class Solution {

public:

    TreeNode* convertBST(TreeNode* root) {

        int sum = ;

        convertCore(root,sum);

        return root;

    }

    void convertCore(TreeNode* root,int &sum){

        if(root == NULL)

            return;

        convertCore(root->right,sum);

        root->val += sum;

        sum = root->val;

        convertCore(root->left,sum);

    }

};

巴特西

leetcode538. Convert BST to Greater Tree

最新文章

热门文章