Swift 解 LeetCode 250:搞懂同值子树,用递归写出权限系统查抄器 ...

打印 上一主题 下一主题

主题 1751|帖子 1751|积分 5253




  
前言

你有没有碰到过这种情况:给你一棵二叉树,要求你找出此中所有“节点值都相同的子树”数目。第一次看到是不是有点懵?我当时就反应了一下:子树、节点值一样、还要统计数目……这到底要怎么下手?

本日我们就来聊聊这道 LeetCode 第 250 题《统计同值子树(Count Univalue Subtrees)》,趁便联合点实际开发中可能碰到的场景,看看这种题到底能学到什么有用的思维方式。
问题描述简单说:

给你一棵二叉树,统计里面有多少个子树,它的所有节点值都一样。
举个例子:
  1.     5
  2.    / \
  3.   1   5
  4. / \   \
  5. 5   5   5
复制代码
上面这个树中,有 4 个“同值子树”:最下面 3 个 5 叶子节点 + 右边那棵 5 -> 5 的子树。
痛点分析:到底难在哪?

这道题看起来像是一道“树的遍历”底子题,但实则不太好把握。
1. 子树的概念搞不清楚

不少人一开始以为是“叶子节点”才叫子树,或者以为只有完整子布局才算。实在任意节点为根的布局都可以是子树。
2. 要不要“递归”?递归从哪开始?

树的问题很多时间都用递归,但递归是“从顶向下”照旧“从底向上”?这题实在是要“从叶子往上走”,由于你得先知道左右子树是否满意条件,才能判断当前节点是不是一个“同值子树”。
3. 怎么“边遍历边判断”?这套路不熟

你不能等遍历完再判断,而是要在每次递归返回的时间就带点有用的信息,比如:是不是同值,是的话加一。

后序遍历 + 全局计数器

  1. class TreeNode {
  2.     var val: Int
  3.     var left: TreeNode?
  4.     var right: TreeNode?
  5.     init(_ val: Int) {
  6.         self.val = val
  7.     }
  8. }
  9. class Solution {
  10.     private var count = 0
  11.     func countUnivalSubtrees(_ root: TreeNode?) -> Int {
  12.         _ = isUnival(root)
  13.         return count
  14.     }
  15.     private func isUnival(_ node: TreeNode?) -> Bool {
  16.         guard let node = node else {
  17.             return true // 空节点默认算同值子树
  18.         }
  19.         let leftIsUnival = isUnival(node.left)
  20.         let rightIsUnival = isUnival(node.right)
  21.         if !leftIsUnival || !rightIsUnival {
  22.             return false
  23.         }
  24.         if let left = node.left, left.val != node.val {
  25.             return false
  26.         }
  27.         if let right = node.right, right.val != node.val {
  28.             return false
  29.         }
  30.         count += 1
  31.         return true
  32.     }
  33. }
复制代码
逻辑很简单:


  • 用一个 count 全局变量做计数器
  • 用一个递归函数 isUnival 判断某节点是不是“同值子树”
  • 每次判断成功就给计数器加一
遍历过程解释一下:

拿刚才的例子图来说:
  1.        5
  2.       / \
  3.      1   5
  4.     / \   \
  5.    5   5   5
复制代码
从最下面开始判断:


  • 左下两个 5 是叶子节点,肯定是同值子树
  • 1 的左右子树固然都是 5,但跟本身不一样,以是不是
  • 右边的 5 -> 5 是同值
  • 整棵树不是,由于左子树不满意
最后统计出来就是 4 个。
和实际场景联合下:这题能学到啥?

说真话,单纯为了刷题记住这题的套路没啥意思。咱们可以想一想,在日常开发中,有没有碰到类似的布局需求?答案是:有。
文件系统权限继续查抄

假设有一个多层级的文件目录布局,你想知道哪些文件夹中,所有子文件的权限都是一样的,这样就可以打包成一个统一模板。


  • 节点 = 文件夹
  • 节点值 = 权限值
  • 子树同值判断 = 查抄子目录权限同等
配置项同等性查抄

比如你有一个配置树,里面可能有很多子配置。如果你想找到哪些配置项完全同等(便于缓存或者合并),这种“统一值的布局辨认”就是这个题的思路。
时间复杂度

这题的时间复杂度是 O(n),由于每个节点最多访问一次。
空间复杂度取决于树的深度,最坏情况是 O(n),也就是退化成链状布局的时间。
测试用例简单跑一下:

  1. let root = TreeNode(5)
  2. root.left = TreeNode(1)
  3. root.right = TreeNode(5)
  4. root.left?.left = TreeNode(5)
  5. root.left?.right = TreeNode(5)
  6. root.right?.right = TreeNode(5)
  7. let solution = Solution()
  8. print(solution.countUnivalSubtrees(root)) // 输出 4
复制代码
最后的话

这题固然在 LeetCode 上是 Easy 难度,但实际含金量挺高:你必要把握“自底向上的遍历”、要会在递归中携带和判断状态、还要明白“布局是否满意条件”的团体判断。
如果你刷题是为了实战开发的思维练习,这种题一定不能只做一遍就忘了,发起把它酿成一张图,标出每个节点是否是同值子树,再动手实现一遍。

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

兜兜零元

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表