手把手带你刷二叉树(第三期)

《算法小抄》纸质书定制寄语,限量 60 本, 点这里 查看~

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

652. 寻找重复的子树(中等)

———–

PS: 刷题插件 集成了手把手刷二叉树功能,按照公式和套路讲解了 150 道二叉树题目,可手把手带你刷完二叉树分类的题目,迅速掌握递归思维。

接前文 手把手带你刷二叉树(第一期)手把手带你刷二叉树(第二期),本文继续来刷二叉树。

从前两篇文章的阅读量来看,大家还是能够通过二叉树学习到 框架思维 的。但还是有不少读者有一些问题,比如如何判断我们应该用前序还是中序还是后序遍历的框架

那么本文就针对这个问题,不贪多,给你掰开揉碎只讲一道题。还是那句话,根据题意,思考一个二叉树节点需要做什么,到底用什么遍历顺序就清楚了

看题,这是力扣第 652 题「寻找重复子树」:

函数签名如下:

List<TreeNode> findDuplicateSubtrees(TreeNode root);

我来简单解释下题目,输入是一棵二叉树的根节点 root,返回的是一个列表,里面装着若干个二叉树节点,这些节点对应的子树在原二叉树中是存在重复的。

说起来比较绕,举例来说,比如输入如下的二叉树:

首先,节点 4 本身可以作为一棵子树,且二叉树中有多个节点 4:

类似的,还存在两棵以 2 为根的重复子树:

那么,我们返回的 List 中就应该有两个 TreeNode,值分别为 4 和 2(具体是哪个节点都无所谓)。

这题咋做呢?还是老套路,先思考,对于某一个节点,它应该做什么

比如说,你站在图中这个节点 2 上:

如果你想知道以自己为根的子树是不是重复的,是否应该被加入结果列表中,你需要知道什么信息?

你需要知道以下两点

1、以我为根的这棵二叉树(子树)长啥样

2、以其他节点为根的子树都长啥样

这就叫知己知彼嘛,我得知道自己长啥样,还得知道别人长啥样,然后才能知道有没有人跟我重复,对不对?

_____________

应合作方要求,本文不便在此发布,请扫码关注回复关键词「二叉树」查看: