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
题目标题:Tree
这道题目给了我们一个二叉搜索树,特性是 left < root < right 对于每一个点。基于这个特性,如果我们要把 每一个点的值 变成 所有比这个点大的sum 再加上它自己,这样的话,我们必须从最右边底下的点开始遍历,因为它是最大的点。设一个sum,利用inorder 来遍历tree, 每次当一个点,它的右边点返回之后,更新sum的值, 用sum = sum + 这个点的val。再把这个点的值更新 = sum。所以根据这个顺序,我们看一下原题给的例子,利用inorder 顺序,结合 right root left 顺序, 我们先一直走到最右边底的点,13, 13右边返回的null, 然后sum = 0 + 13, 13这个点的值就等于sum(13),再去left,这个left返回的也是null。 接着13返回到5这个点, 5的右边点是13, 那么sum = 13+5 (18) 5这个点就更新为18。再去left, 2这个点,2的右边返回的是null, 然后sum = 18 + 2 (20), 再去2的left,null。最后返回到root。
Java Solution:
Runtime beats 89.45%
完成日期:07/07/2017
关键词:Tree
关键点:inorder 来遍历树; 每个点顺序是right, root, left
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
int sum = 0;
public TreeNode convertBST(TreeNode root)
{
if(root == null)
return null; convertBST(root.right); sum += root.val;
root.val = sum; convertBST(root.left); return root;
}
}
参考资料:N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List