0x00 题目
给你一棵根为 root
的二叉树
请你返回二叉树中好节点
的数目
「好节点」X 定义为:
从根到该节点 X
所经过的节点中
没有
任何节点的值大于
X 的值
0x01 思路
经过一个节点时
计算当前路径的最大值
并传递
给下一个节点
通过比较即可判断当前节点是否符合要求
0x02 解法
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
解法:
func goodNodes(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var res: Int = 0
func dfs(_ root: TreeNode?, _ val: Int) {
guard let root = root else { return }
// 是否是好节点
if root.val >= val { res += 1}
// 计算该条路径的最大值
let big = max(root.val, val)
// 递归左右节点
dfs(root.left, big)
dfs(root.right, big)
}
dfs(root, Int.min)
return res
}
0x03 我的小作品
欢迎体验我的作品之一:小编辑器-XCompiler
小巧的在线编辑器
包含多种语言
App Store
搜索即可~
原文地址:https://blog.csdn.net/xjh093/article/details/126013157
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_26138.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。