• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

输入: 
    1
   / \
  0   2

  L = 1
  R = 2

输出: 
    1
      \
       2

示例 2:

输入: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

输出: 
      3
     / 
   2   
  /
 1

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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode114.二叉树展开为链表|FlattenBinaryTreetoLinkedList发布时间:2022-07-13
下一篇:
iOS开发之Swift篇(1)—— 关于Swift发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap