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:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
解释下题目:
给定一颗二分搜索树,对每个节点进行如此操作:将所有比它大的数字加起来,加到它上面
1. 递归
实际耗时:xxms
int globalSum = 0;
public TreeNode convertBST(TreeNode root) {
convert(root);
return root;
}
public void convert(TreeNode cur) {
if (cur == null) {
return;
}
convert(cur.right);
cur.val += globalSum;
globalSum = cur.val;
convert(cur.left);
}
思路:首先确定这是一个二分搜索树,所以大小其实很容易判断,只需要一直往右走,就能找到最大的那个,而最大的那个是不需要加任何数字的;然后找到次小的,这个次小的就需要加上最大的那个数字了。以此进行递归即可得到最后的解。