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

GitHub

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

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

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


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

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

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

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

函数签名如下:

List<TreeNode> findDuplicateSubtrees(TreeNode root);

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

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

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

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

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

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

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

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

你需要知道以下两点

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

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

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

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-03-17 21:09:29

results matching ""

    No results matching ""