东哥带你刷二叉树(后序篇)

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

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(具体是哪个节点都无所谓)。

_____________

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

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释