0652-寻找重复的子树

题目描述

https://leetcode.cn/problems/find-duplicate-subtrees

给定一棵二叉树 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,10^4]范围内。
-200 <= Node.val <= 200

思路分析

起初想到的是暴力解法，用dfs遍历每个节点，然后从那个节点再开始遍历所有节点，最后判断两棵树是否相等，代码如下: 此代码对去重部分逻辑有问题(比如示例1，第3个4的节点，还会被加入)，且节点数时 1-10^4，O(n^3)的时间复杂度会超时

csharp

public class Solution {

    List<TreeNode> list = new List<TreeNode>();
    List<TreeNode> listAll = new List<TreeNode>();

    private bool IsSubTree(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null){
            return true;
        }
        if(node1 == node2){
            return false;
        }
        if(node1 == null || node2 == null){
            return false;
        }
        //Console.WriteLine("node1val:{0},node2val:{1}",node1.val,node2.val);
        if(node1.val != node2.val){
            return false;
        }
        return IsSubTree(node1.left,node2.left) && IsSubTree(node1.right , node2.right);
    }

    private void dfs(TreeNode node1, TreeNode node2){
        if(node1 == null || node2 == null){
            return;
        }
        //Console.WriteLine("dfs:{0} {1}",node1.val,node2.val);
        if(IsSubTree(node1,node2)){
            if(!listAll.Contains(node1) && !listAll.Contains(node1)){
                list.Add(node1);
                listAll.Add(node1);
                listAll.Add(node2);
            }
        }
        dfs(node1.left,node2);
        dfs(node1.right,node2);
        dfs(node1,node2.left);
        dfs(node1,node2.right);
    }

    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        dfs(root,root);
        return list;
    }
}

题解

查看官方题解，使用序列化的方式，将已有的序列化作为key放入hash表中，这样判断key是否存在就知道。序列化的方式是节点值(左节点)(右节点)

csharp

public class Solution {

    Dictionary<string,TreeNode> dict = new Dictionary<string,TreeNode>();
    List<TreeNode> result = new List<TreeNode>();

    private string dfs(TreeNode root){
        if(root == null){
            return "";
        }

        StringBuilder sb = new StringBuilder();
        sb.Append(root.val);
        sb.Append("(");
        sb.Append(dfs(root.left));
        sb.Append(")");
        sb.Append("(");
        sb.Append(dfs(root.right));
        sb.Append(")");
        string key = sb.ToString();
        if(dict.ContainsKey(key)){
            if(!result.Contains(dict[key])){
                result.Add(dict[key]);
            }
        }
        else{
            dict.Add(key,root);
        }
        return key;
    }

    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return result;
    }
}

0652-寻找重复的子树 #

题目描述 #

思路分析 #

题解 #

0652-寻找重复的子树

题目描述

思路分析

题解