乐趣区

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

jiezi

读完本文，你不仅学会了算法套路，还能够顺便去 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;
}

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

退出移动版