LeetCode笔记（538.|LeetCode笔记：538. Convert BST to Greater Tree） LeetCode笔记：538.ConvertBSTtoGrea

问题（Easy）：

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:

文章图片

Output: The root of a Greater Tree like this:

文章图片

大意：

给出一个二叉搜索树（BST），将其转换为更大树，即原本BST中每个节点值都转换为其加上树中所有比它大的节点值之和。
例子：
输入：二叉搜索树如下：

文章图片

【LeetCode笔记（538.|LeetCode笔记：538. Convert BST to Greater Tree）】输出：更大树如下：

文章图片

思路：题目的意思是节点中每个值，都把树中所有比它大的值加起来并加上它自己，就是它的新值。
这肯定要遍历整个树才知道有哪些比一个节点值大的数。因为节点的位置还不能变，所以只能直接在树上操作，这里就要用到二叉搜索树的性质：右大左小。
我们用遍历。
对于每个节点，比它大的节点有：父节点、父节点的右子节点树上所有节点、自己的右子节点、自己的右子节点树上所有节点。所以我们在计算一个节点的新值时，需要把所有这些值都加起来作为自己的新值。
而对于一个节点的左子节点，我们需要将上面算出来的新值给左子节点，这样就是左子节点的“父节点及父节点的右子节点树上所有节点值之和”了。
对于一个节点的右子节点，我们需要将“父节点及父节点的右子节点树上所有节点值之和”给右子节点，因为对于右子节点，它父节点的父节点，及那个节点的右子树，一定都比它大。这里和左子节点给的值其实就不一样了，需要区分计算并供给。
这样我们就可以对每一个节点进行操作，并组成一个递归操作了。
代码（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: int sumValue(TreeNode* root, int toLeft) { int sum = root->val; root->val += toLeft; if (root->right){ int rightValue = https://www.it610.com/article/sumValue(root->right, toLeft); root->val += rightValue; sum += rightValue; } if (root->left) { int leftValue = https://www.it610.com/article/sumValue(root->left, root->val); sum += leftValue; } return sum; }TreeNode* convertBST(TreeNode* root) { if (!root) return root; int temp = sumValue(root, 0); return root; } };

他山之石：其实上面的思路可以再简化一下，先从最大的节点，也就是最右叶子节点开始算，往回退，并用一个全局变量保存一个和，从右子节点，算到节点本身，再算到左子节点，代码简单很多，但是逻辑需要想清楚。

/** * 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 { private: int cur_sum = 0; public: void travel(TreeNode* root){ if (!root) return; if (root->right) travel(root->right); root->val = (cur_sum += root->val); if (root->left) travel(root->left); } TreeNode* convertBST(TreeNode* root) { travel(root); return root; } };

合集：https://github.com/Cloudox/LeetCode-Record
查看作者首页