LeetCode - Medium - 652. Find Duplicate Subtrees

傷城~ 2022-10-08 05:54 27阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/find-duplicate-subtrees/][https_leetcode.com_problems_find-duplicate-subtrees]

Given the `root` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.

**Example 1:**

![da8864fc1ae9a128f6850c69b0e51fc0.png][]

Input: root = [1,2,3,4,null,2,4,null,null,4]
    Output: [[2,4],[4]]

**Example 2:**

![4a32d7bc4d26c877ee71bd9a69714b1f.png][]

Input: root = [2,1,1]
    Output: [[1]]

**Example 3:**

![3b5d98053f22cf7d6ad96cfb32d42378.png][]

Input: root = [2,2,2,3,null,3,null]
    Output: [[2,3],[3]]

**Constraints:**

*  The number of the nodes in the tree will be in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\]
 *   − 200 < = N o d e . v a l < = 200 -200 <= Node.val <= 200 −200<=Node.val<=200

## Analysis ##

子树，也就是从某一节点到叶子节点的范围。如果从上而下遍历，会出现重复遍历的情况。因此，采用从下到上遍历方式，也就是说，用到**后序遍历模式**。

将树序列化成字符串后可方便比较，减少代码量。

用缓存统计树序列化字符串出现次数，刚好有两次，将子树的根节点放入结果集中。

## Submission ##

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindDuplicateSubtrees { 
    	
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) { 
        	List<TreeNode> result = new ArrayList<>();
        	Map<String, Integer> cache = new HashMap<>();
        	findDuplicateSubtrees(root, cache, result);
        	return result;
        }
        
        private String findDuplicateSubtrees(TreeNode node, Map<String, Integer> cache, List<TreeNode> result) { 
        	if(node == null) return "";
        	
        	String left = findDuplicateSubtrees(node.left, cache, result);
        	String right = findDuplicateSubtrees(node.right, cache, result);
        	String thisNode = String.valueOf(node.val);
        	
        	if(!left.equals("")) { 
        		thisNode += ("("+ left +")");
        	}
        	
        	if(!right.equals("")) { 
        		if(left.equals(""))
        			thisNode += "()";
        		thisNode += ("("+ right +")");
        	}
        	
        	int count = cache.getOrDefault(thisNode, 0);
        	if(count == 1) 
        		result.add(node);
        	cache.put(thisNode, count + 1);
        	
        	return thisNode;
        }
    }

## Test ##

import java.util.List;
    
    import static com.lun.util.BinaryTree.integers2BinaryTree;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindDuplicateSubtreesTest { 
    
        @Test
        public void test() { 
            FindDuplicateSubtrees fObj = new FindDuplicateSubtrees();
    
            TreeNode origin1 = integers2BinaryTree(1,2,3,4,null,2,4,null,null,4);
            TreeNode[] expected1 = { integers2BinaryTree(2, 4), integers2BinaryTree(4)};
            List<TreeNode> actual1 = fObj.findDuplicateSubtrees(origin1); 
            assertEquals(2, countCorrect(actual1, expected1));
            
            TreeNode origin2 = integers2BinaryTree(2, 1, 1);
            TreeNode[] expected2 = { integers2BinaryTree(1)};
            List<TreeNode> actual2 = fObj.findDuplicateSubtrees(origin2); 
            assertEquals(1, countCorrect(actual2, expected2));
    
            TreeNode origin3 = integers2BinaryTree(2, 2, 2, 3, null, 3, null);
            TreeNode[] expected3 = { integers2BinaryTree(3), integers2BinaryTree(2,3)};
            List<TreeNode> actual3 = fObj.findDuplicateSubtrees(origin3); 
            assertEquals(2, countCorrect(actual3, expected3));
        }
        
        public int countCorrect(List<TreeNode> actual, TreeNode[] expected) { 
        	if(actual == null || expected == null || actual.size() != expected.length)
        		return 0;
        	int count = 0;
        	for(TreeNode a : actual) { 
        		for(TreeNode e : expected) { 
        			if(BinaryTree.equals(a, e))
        				count++;
        		}
        	}
        	return count;
        }
        
    }

[https_leetcode.com_problems_find-duplicate-subtrees]: https://leetcode.com/problems/find-duplicate-subtrees/
[da8864fc1ae9a128f6850c69b0e51fc0.png]: /images/20221005/61bb464de7bc48a0a5a2922c95f96a53.png
[4a32d7bc4d26c877ee71bd9a69714b1f.png]: /images/20221005/1a5ceebdd18044efad9c242e62c28e50.png
[3b5d98053f22cf7d6ad96cfb32d42378.png]: /images/20221005/d87ceaa92c774e19ba74f97de5c93c94.png