Menu

Subscribe

LeetCode 538 [Convert BST to Greater Tree]

ShuyuFang on Leetcode

题目链接

题目描述

  • 给定一颗二叉排序树，对于每个结点，要求计算出所有比它的值大的结点的值的和，并且将这个计算出来的和加到该结点上面。

解题思路

  1. 首先需要确定如何找到所有比某个结点的值大的其他所有结点。在二叉排序树中，父结点的值总是大于左子树所有结点的值，且小于右子树所有结点的值。所以比某个结点的值大的所有结点，也就是在先序遍历中位于它之后的所有结点。
  2. 本题的要求是将这些结点的值的和加到该结点上面，因此我们不需要逐个查找结点，再逐个加上去，整体处理就可以了。对于每个结点，我们需要记录父结点传下来的增量（简述为“父增量”），它自身变更前的值（简述为“原值”），左子树所有结点变更之前的值的和（简述为“左侧总和”），右子树所有结点变更之前的值的和（简述为“右侧总和”），然后将“原值+右侧总和+父增量”作为增量加到左子树的每个结点上面，将“父增量”作为增量加到右子树的每个结点上，再将“右侧总和+父增量”作为增量加到自身上面。处理左右结点的流程与其父结点是一致的，递归处理即可。
  3. 变更结点的值以及计算当前的树的所有结点的值的总和，这两个流程可以在一次遍历中完成，通过不同的变量来记录变更前后的值即可。

C++代码

/**
 * 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) {
        int rootOriginSum, rootNewSum;
        convertNode(root, rootOriginSum, 0, rootNewSum);
        return root;
    }
    void convertNode(TreeNode* node, int& originSum, int delta, int& newSum) {
        if (!node) {
            originSum = 0;
            newSum = 0;
            return;
        }
        int rightOriginSum, rightNewSum;
        convertNode(node->right, rightOriginSum, delta, rightNewSum);
        int leftOriginSum, leftNewSum;
        convertNode(node->left, leftOriginSum, delta + node->val + rightOriginSum, leftNewSum);
        originSum = node->val + leftOriginSum + rightOriginSum;
        node->val += delta + rightOriginSum;
        newSum = node->val + leftNewSum + rightNewSum;
    }
};