关于算法:东哥手把手带你刷二叉树第三期

47次阅读

共计 2873 个字符,预计需要花费 8 分钟才能阅读完成。

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

652. 寻找反复的子树

———–

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

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

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

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

函数签名如下:

List<TreeNode> findDuplicateSubtrees(TreeNode root);

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

说起来比拟绕,举例来说,比方输出如下的二叉树:

首先,节点 4 自身能够作为一棵子树,且二叉树中有多个节点 4:

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

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

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

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

如果你想晓得以本人为根的子树是不是反复的,是否应该被退出后果列表中,你须要晓得什么信息?

你须要晓得以下两点

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

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

这就叫知己知彼嘛,我得晓得本人长啥样,还得晓得他人长啥样,而后能力晓得有没有人跟我反复,对不对?

好,那咱们一个一个来看,先来思考,我如何能力晓得以本人为根的二叉树长啥样

其实看到这个问题,就能够判断本题要应用「后序遍历」框架来解决:

void traverse(TreeNode root) {traverse(root.left);
    traverse(root.right);
    /* 解法代码的地位 */
}

为什么?很简略呀,我要晓得以本人为根的子树长啥样,是不是得先晓得我的左右子树长啥样,再加上本人,就形成了整棵子树的样子?

如果你还绕不过去,我再来举个非常简单的例子:计算一棵二叉树有多少个节点。这个代码应该会写吧:

int count(TreeNode root) {if (root == null) {return 0;}
    // 先算出左右子树有多少节点
    int left = count(root.left);
    int right = count(root.right);
    /* 后序遍历代码地位 */
    // 加上本人,就是整棵二叉树的节点数
    int res = left + right + 1;
    return res;
}

这不就是规范的后序遍历框架嘛,和咱们本题在实质上没啥区别对吧。

当初,明确了要用后序遍历,那应该怎么形容一棵二叉树的模样呢?咱们前文 序列化和反序列化二叉树 其实写过了,二叉树的前序 / 中序 / 后序遍历后果能够形容二叉树的构造。

所以,咱们能够通过拼接字符串的形式把二叉树序列化,看下代码:

String traverse(TreeNode root) {
    // 对于空节点,能够用一个特殊字符示意
    if (root == null) {return "#";}
    // 将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* 后序遍历代码地位 */
    // 左右子树加上本人,就是以本人为根的二叉树序列化后果
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}

咱们用非数字的非凡符 # 示意空指针,并且用字符 , 分隔每个二叉树节点值,这属于序列化二叉树的套路了,不多说。

留神咱们 subTree 是依照左子树、右子树、根节点这样的程序拼接字符串,也就是后序遍历程序。你齐全能够依照前序或者中序的程序拼接字符串,因为这里只是为了形容一棵二叉树的样子,什么程序不重要。

这样,咱们第一个问题就解决了,对于每个节点,递归函数中的 subTree 变量就能够形容以该节点为根的二叉树

当初咱们解决第二个问题,我晓得了本人长啥样,怎么晓得他人长啥样?这样我能力晓得有没有其余子树跟我反复对吧。

这很简略呀,咱们借助一个内部数据结构,让每个节点把本人子树的序列化后果存进去,这样,对于每个节点,不就能够晓得有没有其余节点的子树和本人反复了么?

初步思路能够应用 HashSet 记录子树,代码如下:

// 记录所有子树
HashSet<String> memo = new HashSet<>();
// 记录反复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

String traverse(TreeNode root) {if (root == null) {return "#";}

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    if (memo.contains(subTree)) {
        // 有人和我反复,把本人退出后果列表
        res.add(root);
    } else {
        // 临时没人跟我反复,把本人退出汇合
        memo.add(subTree);
    }
    return subTree;
}

然而呢,这有个问题,如果呈现多棵反复的子树,后果集 res 中必然呈现反复,而题目要求不心愿呈现反复。

为了解决这个问题,能够把 HashSet 升级成 HashMap,额定记录每棵子树的呈现次数:

// 记录所有子树以及呈现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录反复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {traverse(root);
    return res;
}

/* 辅助函数 */
String traverse(TreeNode root) {if (root == null) {return "#";}

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;
    
    int freq = memo.getOrDefault(subTree, 0);
    // 多次重复也只会被退出后果集一次
    if (freq == 1) {res.add(root);
    }
    // 给子树对应的呈现次数加一
    memo.put(subTree, freq + 1);
    return subTree;
}

这样,这道题就齐全解决了,题目自身算不上难,然而思路拆解下来还是挺有启发性的吧?

正文完
 0