Swift 解 LeetCode 250：搞懂同值子树，用递归写出权限系统查抄器
https://i-blog.csdnimg.cn/direct/565ae998d0be43cb80d488f660a12704.png#pic_centerhttps://i-blog.csdnimg.cn/blog_migrate/aadffb113c7529bb0a991c3f73e8f846.gif
前言
你有没有碰到过这种情况：给你一棵二叉树，要求你找出此中所有“节点值都相同的子树”数目。第一次看到是不是有点懵？我当时就反应了一下：子树、节点值一样、还要统计数目……这到底要怎么下手？
https://i-blog.csdnimg.cn/direct/033fb49516be49f08d7533c3cc0df26d.png
本日我们就来聊聊这道 LeetCode 第 250 题《统计同值子树（Count Univalue Subtrees）》，趁便联合点实际开发中可能碰到的场景，看看这种题到底能学到什么有用的思维方式。
问题描述简单说：
给你一棵二叉树，统计里面有多少个子树，它的所有节点值都一样。
举个例子：
5
/ \
1 5
/ \ \
5 5 5
上面这个树中，有 4 个“同值子树”：最下面 3 个 5 叶子节点 + 右边那棵 5 -> 5 的子树。
痛点分析：到底难在哪？
这道题看起来像是一道“树的遍历”底子题，但实则不太好把握。
1. 子树的概念搞不清楚
不少人一开始以为是“叶子节点”才叫子树，或者以为只有完整子布局才算。实在任意节点为根的布局都可以是子树。
2. 要不要“递归”？递归从哪开始？
树的问题很多时间都用递归，但递归是“从顶向下”照旧“从底向上”？这题实在是要“从叶子往上走”，由于你得先知道左右子树是否满意条件，才能判断当前节点是不是一个“同值子树”。
3. 怎么“边遍历边判断”？这套路不熟
你不能等遍历完再判断，而是要在每次递归返回的时间就带点有用的信息，比如：是不是同值，是的话加一。
https://i-blog.csdnimg.cn/direct/a0d338fa17054066953ec43bb8f178a1.png
后序遍历 + 全局计数器
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
}
}
class Solution {
private var count = 0
func countUnivalSubtrees(_ root: TreeNode?) -> Int {
_ = isUnival(root)
return count
}
private func isUnival(_ node: TreeNode?) -> Bool {
guard let node = node else {
return true // 空节点默认算同值子树
}
let leftIsUnival = isUnival(node.left)
let rightIsUnival = isUnival(node.right)
if !leftIsUnival || !rightIsUnival {
return false
}
if let left = node.left, left.val != node.val {
return false
}
if let right = node.right, right.val != node.val {
return false
}
count += 1
return true
}
}
逻辑很简单：
[*]用一个 count 全局变量做计数器
[*]用一个递归函数 isUnival 判断某节点是不是“同值子树”
[*]每次判断成功就给计数器加一
遍历过程解释一下：
拿刚才的例子图来说：
5
/ \
1 5
/ \ \
5 5 5
从最下面开始判断：
[*]左下两个 5 是叶子节点，肯定是同值子树
[*]1 的左右子树固然都是 5，但跟本身不一样，以是不是
[*]右边的 5 -> 5 是同值
[*]整棵树不是，由于左子树不满意
最后统计出来就是 4 个。
和实际场景联合下：这题能学到啥？
说真话，单纯为了刷题记住这题的套路没啥意思。咱们可以想一想，在日常开发中，有没有碰到类似的布局需求？答案是：有。
文件系统权限继续查抄
假设有一个多层级的文件目录布局，你想知道哪些文件夹中，所有子文件的权限都是一样的，这样就可以打包成一个统一模板。
[*]节点 = 文件夹
[*]节点值 = 权限值
[*]子树同值判断 = 查抄子目录权限同等
配置项同等性查抄
比如你有一个配置树，里面可能有很多子配置。如果你想找到哪些配置项完全同等（便于缓存或者合并），这种“统一值的布局辨认”就是这个题的思路。
时间复杂度
这题的时间复杂度是 O(n)，由于每个节点最多访问一次。
空间复杂度取决于树的深度，最坏情况是 O(n)，也就是退化成链状布局的时间。
测试用例简单跑一下：
let root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(5)
root.left?.left = TreeNode(5)
root.left?.right = TreeNode(5)
root.right?.right = TreeNode(5)
let solution = Solution()
print(solution.countUnivalSubtrees(root)) // 输出 4
最后的话
这题固然在 LeetCode 上是 Easy 难度，但实际含金量挺高：你必要把握“自底向上的遍历”、要会在递归中携带和判断状态、还要明白“布局是否满意条件”的团体判断。
如果你刷题是为了实战开发的思维练习，这种题一定不能只做一遍就忘了，发起把它酿成一张图，标出每个节点是否是同值子树，再动手实现一遍。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]