由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁」
按照操作即可解锁本站全部文章
数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
LeetCode | 力扣 | 难度 |
---|---|---|
652. Find Duplicate Subtrees | 652. 寻找重复的子树 | 🟠 |
———–
在开头先打个广告,我的 手把手刷二叉树课程 按照公式和套路讲解了 150 道二叉树题目,只需一顿饭钱,就能手把手带你刷完二叉树分类的题目,迅速掌握递归思维,让你豁然开朗。我绝对有这个信心,信不信,可以等你看完我的二叉树算法系列文章再做评判。
本文是承接 东哥带你刷二叉树(纲领篇) 的第四篇文章,主要讲二叉树后序位置的妙用,复述下前文关于后序遍历的描述:
前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据。
那么换句话说,一旦你发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了。
多说无益,我们直接看题,这是力扣第 652 题「 寻找重复的子树」:
函数签名如下:
List<TreeNode> findDuplicateSubtrees(TreeNode root);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
def findDuplicateSubtrees(root: TreeNode) -> List[TreeNode]:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var findDuplicateSubtrees = function(root) {}
我来简单解释下题目,输入是一棵二叉树的根节点 root
,返回的是一个列表,里面装着若干个二叉树节点,这些节点对应的子树在原二叉树中是存在重复的。
说起来比较绕,举例来说,比如输入如下的二叉树:
首先,节点 4 本身可以作为一棵子树,且二叉树中有多个节点 4:
类似的,还存在两棵以 2 为根的重复子树:
那么,我们返回的 List
中就应该有两个 TreeNode
,值分别为 4 和 2(具体是哪个节点都无所谓)。
_____________
应合作方要求,本文不便在此发布,请扫码关注回复关键词「二叉树」或 点这里 查看:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释