LeetCode 538 [Convert BST to Greater Tree]

题目链接

题目描述

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

解题思路

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

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 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;
}
};