本文介绍: 题目给你一棵根为 root二叉树请你返回二叉树中好节点数目「好节点」X 定义为:从根到该节点 X 所经过的节点中没有任何节点的值大于 X 的值

0x00 题目

给你一棵根为 root二叉树
请你返回二叉树好节点的数目

「好节点」X 定义为:
从根到该节点 X 所经过的节点中
没有任何节点的值大于 X 的值


0x01 思路

经过一个节点时
计算当前路径最大值
传递给下一个节点
通过比较即可判断当前节点是否符合要求


0x02 解法

语言Swift

树节点:TreeNode

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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注