跳至主要內容

 

labuladong约 1305 字大约 4 分钟数据结构二叉树分解问题的思路

Info

数据结构精品课open in new window递归算法专题课open in new window 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》open in new window 出版,签名版限时半价!

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

LeetCode力扣难度
652. Find Duplicate Subtreesopen in new window652. 寻找重复的子树open in new window🟠

Info

在开头先打个广告,我的 手把手刷二叉树课程open in new window 按照公式和套路讲解了 150 道二叉树题目,只需一顿饭钱,就能手把手带你刷完二叉树分类的题目,迅速掌握递归思维,让你豁然开朗。我绝对有这个信心,信不信,可以等你看完我的二叉树算法系列文章再做评判。

本文是承接 东哥带你刷二叉树(纲领篇) 的第四篇文章,主要讲二叉树后序位置的妙用,复述下前文关于后序遍历的描述:

前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据。

那么换句话说,一旦你发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了

多说无益,我们直接看题,这是力扣第 652 题「寻找重复的子树open in new window」:

652. 寻找重复的子树 | 力扣 open in new window | LeetCode open in new window |

给你一棵二叉树的根节点 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

函数签名如下:

List<TreeNode> findDuplicateSubtrees(TreeNode root);

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

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

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

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

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

本文剩余内容为会员内容,请先购买 网站会员 open in new window ,然后 借助 Chrome 插件解锁网页 open in new window 或者 点这里open in new window 跳转小鹅通查看。

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