[Swift]LeetCode538.把二叉搜索树转换为累加树|ConvertBSTtoGreaterTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9817299.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

给定一个二叉搜索树（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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     private var sum = 0
16     func convertBST(_ root: TreeNode?) -> TreeNode? {
17        // in-order dfs
18         if root != nil {
19         convertBST(root?.right)
20         sum += root!.val
21         root!.val = sum
22         convertBST(root?.left)
23         }
24         return root
25     }
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 = nil
10  *         self.right = nil
11  *     }
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 root
22     }
23     
24     var sum = 0
25     
26     func traverse(_ root: TreeNode?) {
27         guard let root = root else { return }
28         
29         traverse(root.right)
30         sum += root.val
31         root.val = sum
32         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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     
16     var sum = 0
17     
18     func convertBST(_ root: TreeNode?) -> TreeNode? {
19         if root == nil {
20             return root  
21         } 
22         convertBST(root!.right)
23         root!.val = root!.val + sum
24         sum = root!.val
25         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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15      func convertBST(_ root: TreeNode?) -> TreeNode? {
16         var sum = 0
17          var stack = Stack()
18          
19         var node = root
20          
21          while !stack.isEmpty || node != nil {
22              while node != nil {
23                  stack.push(node!)
24                  node = node?.right
25              }
26              
27              node = stack.pop()
28              sum += node!.val
29              node!.val = sum
30              
31              node = node?.left
32          }
33          
34          return root
35     }
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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func convertBST(_ root: TreeNode?) -> TreeNode? {
16         _ = convertBST(root, 0)
17         return root
18     }
19 
20     func convertBST(_ root: TreeNode?, _ num: Int) -> Int {
21         guard let root = root else {
22             return num
23         }
24         
25         var num = convertBST(root.right, num)
26         root.val += num
27         num = root.val
28         num = convertBST(root.left, num)
29         return num
30     }
31 }