[Swift]LeetCode669.修剪二叉搜索树|TrimaBinarySearchTree

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

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

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

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

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

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

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2

Example 2:

Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:

示例 2:

68ms

 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 trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
16         guard let r = root else { return nil }
17         
18         if r.val > R { return trimBST(r.left, L, R) }
19         if r.val < L { return trimBST(r.right, L, R) }
20         
21         r.left = trimBST(r.left, L, R)
22         r.right = trimBST(r.right, L, R)
23         
24         return r
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     func trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
16         guard let root = root else {
17             return nil 
18         }
19         
20         var resultTree: TreeNode? = nil 
21         preorderTraversal(root) {
22             val in 
23             if val >= L && val <= R {
24                 resultTree = addNode(resultTree, val)
25             }
26         }
27         return resultTree
28     }
29 }
30 
31 func addNode(_ root: TreeNode?, _ val: Int) -> TreeNode {
32     guard let root = root else {
33         return TreeNode(val)
34     }
35     
36     if val <= root.val {
37         root.left = addNode(root.left, val)
38     } else {
39         root.right = addNode(root.right, val)
40     }
41     return root
42 }
43 
44 func preorderTraversal(_ root: TreeNode?, _ visit: (Int) -> Void) {
45     guard let root = root else {
46         return 
47     }
48     visit(root.val)
49     preorderTraversal(root.left, visit)
50     preorderTraversal(root.right, visit)
51 }

96ms

 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 trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
16         guard let r = root else {
17             return nil 
18         }
19         if r.val < L {
20             return trimBST(r.right, L, R)
21         } else if r.val > R {
22             return trimBST(r.left, L, R)
23         }
24         r.left = trimBST(r.left, L, R)
25         r.right = trimBST(r.right, L, R)
26         return r
27     }
28     
29     func deleteNode(_ node: TreeNode) -> TreeNode?{
30         if node.left == nil {
31             return node.right
32         } else if node.right == nil {
33             return node.left
34         } else {
35             return insert(root: node.left, node: node.right!)
36         }
37     }
38     
39     func insert(root: TreeNode?, node: TreeNode) -> TreeNode {
40         guard var n = root else {
41             return node
42         }
43         
44         if node.val < n.val {
45             if n.left == nil {
46                 n.left = node
47             } else {
48                 n.left = insert(root: n.left, node: node)
49             }
50         } else {
51             if n.right == nil {
52                 n.right = node
53             } else {
54                 n.right = insert(root: n.right, node: node)
55             }
56         }
57         
58         return node
59     }
60 }