538 Convert BST to Greater Tree

题目

538 Convert BST to Greater Tree

题解

笨方法：

1. 求出每棵子树的节点值总和
2. 每个节点node的值减去它的左孩子节点的值。这一步把所有比node更小的节点都排除了
3. 每个节点把自己的值parent传给左孩子节点进行更新。这是为了把来自父节点及其右子树的节点值之和补上，因为对于一个节点node，node的值不仅小于它的右子树中的节点值，同时也比其父节点以及父节点右子树中的节点值要小
4. 子节点child收到parent值后，将自己的值加上parent，再把更新后的自己的值传给child的左孩子节点进行更新

a clever way：

1. 初始化一个全局变量sum为0
2. 对BST进行反向中序遍历，即按照右孩子节点→根节点→左孩子节点的方式遍历。
3. 在遍历过程中将节点的值累加到变量sum中，并用当前的sum值创建一个新节点。

因为对BST的反向中序遍历会从大到小有序地遍历所有节点，所以计算出来的sum值自然就是所有比当前节点值要大的节点值之和。

复杂度分析

两种方法都只需遍历BST常数次，因此时间复杂度都为\(O(n)\)；遍历时占用的栈空间与树的深度有关，而BST在极端情况下深度为n，故空间复杂度为\(O(n)\)。

代码

笨方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
  public:
    TreeNode *convertBST(TreeNode *root)
    {
        TreeNode *result = sumUpRecursive(root);
        subtractSmaller(result);
        addGreater(result, 0);
        return result;
    }

    TreeNode *sumUpRecursive(TreeNode *root)
    {
        if (root == NULL)
        {
            return NULL;
        }

        TreeNode *leftChild = sumUpRecursive(root->left);
        TreeNode *rightChild = sumUpRecursive(root->right);

        int leftValue = leftChild == NULL ? 0 : leftChild->val;
        int rightValue = rightChild == NULL ? 0 : rightChild->val;

        TreeNode *node = new TreeNode(root->val);
        node->left = leftChild;
        node->right = rightChild;
        node->val += leftValue + rightValue;
        return node;
    }

    void subtractSmaller(TreeNode *root)
    {
        if (root == NULL)
        {
            return;
        }

        if (root->left != NULL)
        {
            root->val -= root->left->val;
        }
        subtractSmaller(root->left);
        subtractSmaller(root->right);
    }

    void addGreater(TreeNode *root, int greaterSumFromParent)
    {
        if (root == NULL)
        {
            return;
        }
        root->val += greaterSumFromParent;
        addGreater(root->left, root->val);
        addGreater(root->right, greaterSumFromParent);
    }
};