leetcode652-寻找重复的子树

原题

给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例1:

    1  
   / \  
  2   3  
 /   / \  
4   2   4      
   /    
  4

下面是两个重复的子树:

  2  
 /    
4  

4

因此,你需要以列表的形式返回上述重复子树的根结点。

解法

思想

将子树按照某种算法遍历序列化成字符串,作为哈希表的键。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<String,Integer> map;
    List<TreeNode> list;
    public String LRD(TreeNode node){
        StringBuilder sb = new StringBuilder();
        dfs(sb,node);
        return sb.toString();
    }
    public void dfs(StringBuilder str,TreeNode node){
        if(node == null){
            str.append('n');
            return;
        }
        dfs(str,node.left);
        dfs(str,node.right);
        str.append(String.valueOf(node.val));
        return;
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        list = new ArrayList<>();
        dfsFindSubtrees(root);
        return list;
    }
    public void dfsFindSubtrees(TreeNode root){
        if(root == null) return;
        dfsFindSubtrees(root.left);
        dfsFindSubtrees(root.right);
        String LRD = LRD(root);
        if(map.containsKey(LRD)){
            if(map.get(LRD)==1){
                list.add(root);
                map.put(LRD,0);
            }
        }else{
            map.put(LRD,1);
        }
    }
} 

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode652-%e5%af%bb%e6%89%be%e9%87%8d%e5%a4%8d%e7%9a%84%e5%ad%90%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月26日 13:25
下一篇 2019年12月26日

相关推荐

  • 剑指offer35-复杂链表的复制

    原题(来源Leetcode) 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random …

    2020年6月13日
    0110
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0180
  • 剑指offer57-和为s的连续正数序列

    原题(来源Leetcode) 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。 序列内的数字由小到大排列,不同序列按照首个数字从小到…

    算法 2020年3月6日
    060
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode21-合并两个有序链表

    原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入: 1->2->4, 1->3->4 输出: 1->1->2->3-…

    2019年12月17日
    0100
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0120
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    080
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输…

    算法 2020年5月23日
    0170

发表回复

登录后才能评论