★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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 13Output: The root of a Greater Tree like this: 18 / \ 20 13
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / \ 20 13
80ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 private var sum = 016 func convertBST(_ root: TreeNode?) -> TreeNode? {17 // in-order dfs18 if root != nil {19 convertBST(root?.right)20 sum += root!.val21 root!.val = sum22 convertBST(root?.left)23 }24 return root25 }26 } 84ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 16 func convertBST(_ root: TreeNode?) -> TreeNode? {17 guard let root = root else { return nil }18 19 traverse(root)20 21 return root22 }23 24 var sum = 025 26 func traverse(_ root: TreeNode?) {27 guard let root = root else { return }28 29 traverse(root.right)30 sum += root.val31 root.val = sum32 traverse(root.left)33 }34 } 92ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 16 var sum = 017 18 func convertBST(_ root: TreeNode?) -> TreeNode? {19 if root == nil {20 return root 21 } 22 convertBST(root!.right)23 root!.val = root!.val + sum24 sum = root!.val25 convertBST(root!.left)26 27 return root 28 } 29 } 100ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func convertBST(_ root: TreeNode?) -> TreeNode? {16 var sum = 017 var stack = Stack()18 19 var node = root20 21 while !stack.isEmpty || node != nil {22 while node != nil {23 stack.push(node!)24 node = node?.right25 }26 27 node = stack.pop()28 sum += node!.val29 node!.val = sum30 31 node = node?.left32 }33 34 return root35 }36 }37 38 class Stack {39 private var array = [TreeNode]()40 41 var isEmpty: Bool { return array.isEmpty }42 43 func push(_ node: TreeNode) {44 array.append(node)45 }46 47 func pop() -> TreeNode {48 return array.popLast()!49 }50 } 120ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func convertBST(_ root: TreeNode?) -> TreeNode? {16 _ = convertBST(root, 0)17 return root18 }19 20 func convertBST(_ root: TreeNode?, _ num: Int) -> Int {21 guard let root = root else {22 return num23 }24 25 var num = convertBST(root.right, num)26 root.val += num27 num = root.val28 num = convertBST(root.left, num)29 return num30 }31 }