跳至主要內容

 

labuladong原创数据结构二叉树分解问题的思路约 2172 字大约 7 分钟

Info

新版网站会员open in new window 限时优惠;算法可视化编辑器上线,点击体验open in new window

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

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

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

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

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

多说无益,我们直接看题,这是力扣第 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

函数签名如下:

java 🟢
List<TreeNode> findDuplicateSubtrees(TreeNode root);

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

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

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

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

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

加载中...

上次编辑于: