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

[Swift]LeetCode1038.从二叉搜索树到更大和树|BinarySearchTreetoGreaterSumTree ...

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Note:

  1. The number of nodes in the tree is between 1 and 100.
  2. Each node will have value between 0 and 100.
  3. The given tree is a binary search tree.

给出二叉搜索树的根节点,该二叉树的节点值各不相同,修改二叉树,使每个节点 node 的新值等于原树的值之和,这个值应该大于或等于 node.val

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键小于节点键的节点。
  • 节点的右子树仅包含键大于节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例:

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

提示:

  1. 树中的节点数介于 1 和 100 之间。
  2. 每个节点的值介于 0 和 100 之间。
  3. 给定的树为二叉搜索树。

Runtime: 8 ms
Memory Usage: 19.2 MB
 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 bstToGst(_ root: TreeNode?) -> TreeNode? {
16         var root = root
17         var acc:Int = 0
18         dfs(&root,&acc)
19         return root        
20     }
21     
22     func dfs(_ node:inout TreeNode?,_ acc:inout Int)
23     {
24         if node != nil
25         {
26             dfs(&node!.right, &acc)
27             var temp:Int = node!.val
28             node!.val += acc
29             acc += temp
30             dfs(&node!.left, &acc)
31         }        
32     }
33 }

8ms 
 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      var sum = 0;
16     func bstToGst(_ root: TreeNode?) -> TreeNode? {
17         
18         guard let rootd = root else {return nil}
19         bstToGst(rootd.right);
20         rootd.val += sum;
21         sum = rootd.val;
22         bstToGst(rootd.left);
23         return rootd
24         
25     }
26 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
swift的高阶函数的使用代码发布时间:2022-07-13
下一篇:
今日份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