/*
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.
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
*/
class Convert_BST_to_Greater_Tree: NSObject {
var sum = 0
func convertBST(_ root: TreeNode?) -> TreeNode? {
convert(root)
return root
}
func convert(_ root: TreeNode?) {
if root == nil {
return
} else {
convert(root?.right)
root!.val += sum;
sum = root!.val;
convert(root?.left)
}
}
}
Convert_BST_to_Greater_Tree
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 这道题让我们将二叉搜索树转为较大树，通过题目汇总的例子可以明白，是把每个结点值加上所有比它大的结点值总和当作新的结...
- 这道题我一开始没看清是BST，以为只是普通binary tree. 一开始觉得会很麻烦，后来发现是BST，那么要f...
- tag 上说是 tree 类型的题目，但我觉得这更像是一个 backtracking的题目 解法： 因为题目要求所...
- 二叉树的题目挺多的，写了个初始化二叉树的函数，以后用 题目 Given a Binary Search Tree ...
