东哥带你刷二叉树(后序篇)
原创数据结构二叉树分解问题的思路约 2930 字
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
652. Find Duplicate Subtrees | 652. 寻找重复的子树 | 🟠 |
本文是承接 东哥带你刷二叉树(纲领篇) 的第四篇文章,主要讲二叉树后序位置的妙用,复述下前文关于后序遍历的描述:
前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据。
那么换句话说,一旦你发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了。
多说无益,我们直接看题,这是力扣第 652 题「寻找重复的子树」:
652. 寻找重复的子树 | 力扣 | LeetCode |
给你一棵二叉树的根节点 root
,返回所有 重复的子树 。
对于同一类的重复子树,你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ,则认为二者是 重复 的。
示例 1:
输入:root = [1,2,3,4,null,2,4,null,null,4] 输出:[[2,4],[4]]
示例 2:
输入:root = [2,1,1] 输出:[[1]]
示例 3:
输入:root = [2,2,2,3,null,3,null] 输出:[[2,3],[3]]
提示:
- 树中的结点数在
[1, 5000]
范围内。 -200 <= Node.val <= 200
java 🟢
// 函数签名如下
List<TreeNode> findDuplicateSubtrees(TreeNode root);
cpp 🤖
// 函数签名如下
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root);
python 🤖
# 函数签名如下
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
go 🤖
// 函数签名如下
func findDuplicateSubtrees(root *TreeNode) []*TreeNode
javascript 🤖
// 函数签名如下
var findDuplicateSubtrees = function(root) {}
我来简单解释下题目,输入是一棵二叉树的根节点 root
,返回的是一个列表,里面装着若干个二叉树节点,这些节点对应的子树在原二叉树中是存在重复的。
说起来比较绕,举例来说,比如输入如下的二叉树:
![](/algo/images/%E4%BA%8C%E5%8F%89%E6%A0%913/1.png)
首先,节点 4 本身可以作为一棵子树,且二叉树中有多个节点 4:
![](/algo/images/%E4%BA%8C%E5%8F%89%E6%A0%913/2.png)
类似的,还存在两棵以 2 为根的重复子树:
![](/algo/images/%E4%BA%8C%E5%8F%89%E6%A0%913/3.png)
那么,我们返回的 List
中就应该有两个 TreeNode
,值分别为 4 和 2(具体是哪个节点都无所谓)。