[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees（寻找重复数leetcode）

25-04-17 3

对于[Swift]LeetCode652.寻找重复的子树|FindDuplicateSubtrees感兴趣的读者，本文将提供您所需要的所有信息，我们将详细讲解寻找重复数leetcode，并且为您提供关

对于[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees感兴趣的读者，本文将提供您所需要的所有信息，我们将详细讲解寻找重复数leetcode，并且为您提供关于0287. Find the Duplicate Number (M)、250. Count Univalue Subtrees - Medium、287. Find the Duplicate Number、652. Find Duplicate Subtrees的宝贵知识。

本文目录一览：

[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees（寻找重复数leetcode）
0287. Find the Duplicate Number (M)
250. Count Univalue Subtrees - Medium
287. Find the Duplicate Number
652. Find Duplicate Subtrees

[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees（寻找重复数leetcode）

Given 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 same node values.

Example 1:

        1
       /       2   3
     /   /     4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

Therefore,you need to return above trees‘ root in the form of a list.

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

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

示例 1：

        1
       /       2   3
     /   /     4   2   4
       /
      4

下面是两个重复的子树：

      2
     /
    4

和

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

Runtime: 72 ms

Memory Usage: 26.2 MB

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
16         var res:[TreeNode?] = [TreeNode?]()
17         var m:[String:Int] = [String:Int]()
18         helper(root,&m,&res)
19         return res
20     }
21     
22     func helper(_ node: TreeNode?,_ m:inout [String:Int],_ res:inout [TreeNode?]) -> String
23     {
24         if node == nil {return "#"}
25         var str:String = String(node!.val) + "," + helper(node!.left,&res) + "," + helper(node!.right,&res)
26         if m[str] == 1
27         {
28             res.append(node)
29         }
30         m[str,default:0] += 1
31         return str
32     }
33 }

72ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
16         var map = [String: Int]()
17         var result = [TreeNode?]()
18         var inorderT = findDuplicateSubtrees(root,&map,&result)
19         
20         return result
21     }
22     
23     func findDuplicateSubtrees(_ root: TreeNode?,_ map: inout [String: Int],_ result: inout [TreeNode?]) -> String {
24         guard let root = root else { 
25             return ""
26         }
27         
28         var str = "("
29         str += findDuplicateSubtrees(root.left,&result)
30         str += "\(root.val)"
31         str += findDuplicateSubtrees(root.right,&result)
32         str += ")"
33         
34         map[str] = (map[str] ?? 0) + 1
35         
36         if map[str] == 2 {
37             result.append(root)
38         }
39         
40         return str                                
41     }
42 }

72ms

 1 /**
 2  * DeFinition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
16         var res:[TreeNode?] = [TreeNode?]()
17         var m:[String:Int] = [String:Int]()
18         helper(root,default:0] += 1
31         return str
32     }
33 }

88ms

 1 class Solution {
 2     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
 3         var result = [TreeNode]()
 4         var dict = [String: Int]()
 5         helper(&result,&dict,root)
 6         return result
 7     }
 8     
 9     func helper(_ result: inout [TreeNode],_ dict: inout [String: Int],_ root: TreeNode?) -> String {
10         guard let root = root else { return "#" }
11         
12         let left = helper(&result,root.left)
13         let right = helper(&result,root.right)
14         
15         let s = "\(root.val)" + "," + left + "," + right        
16         if let count = dict[s] {
17             if count == 1 {
18                 result.append(root)
19             }
20             dict[s] = count + 1
21         } else {
22             dict[s] = 1
23         }
24         
25         return s
26     }
27 }

92ms

 1 class Solution {
 2     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
 3         var subTree: [String: Int] = [:]
 4         var res: [TreeNode?] = []
 5         helper(root,&subTree,&res)
 6         return res
 7     }
 8     
 9     private func helper(_ root: TreeNode?,_ subTree: inout [String: Int],_ res: inout [TreeNode?]) -> String {
10         guard let root = root else { return "#" }
11         let serializedString = "\(String(root.val)) \(helper(root.left,&res)) \(helper(root.right,&res))"
12         
13         if let count = subTree[serializedString] {
14             if count == 1 {
15                 res.append(root)
16             }
17             subTree[serializedString] = count + 1
18         } else {
19             subTree[serializedString] = 1
20         }
21         
22         return serializedString
23     }
24 }

96ms

 1 class Solution {
 2     var foundSubtrees = Set<String>()
 3     var solution = [String: TreeNode]()
 4     
 5     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
 6         guard let root = root else { return [] }
 7         solve(root)
 8         return [TreeNode](solution.values)
 9     }
10     
11     func solve(_ node: TreeNode) -> String {
12         let leftKey = node.left.map { return solve($0) } ?? "NL"
13         let rightKey = node.right.map { return solve($0) } ?? "NR"
14         let key = "[\(String(node.val))/\(leftKey):\(rightKey)]"
15         if foundSubtrees.contains(key) {
16             solution[key] = node
17         } else {
18             foundSubtrees.insert(key)
19         }
20         return key
21     }
22 }
23 
24 extension TreeNode: Hashable {
25     public var hashValue: Int {
26         return val
27     }
28     
29     static public func == (lhs: TreeNode,rhs: TreeNode) -> Bool {
30         return lhs.val == rhs.val
31     }
32 }

100ms

 1 class Solution {
 2     var res: [TreeNode?] = []
 3     var map: [String: Int] = [:]
 4     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
 5         preorder(root)
 6         return res
 7     }
 8     
 9     private func preorder(_ root: TreeNode?) -> String {
10         
11         guard let root = root else { return "#"}
12         let serial = "\(root.val),\(preorder(root.left)),\(preorder(root.right))"
13         if map[serial] == 1 { res.append(root) }
14         
15         map[serial,default: 0] += 1
16         return serial
17     }
18 }

104ms

 1 class Solution {
 2     var ans = [TreeNode]()
 3     var subTrees = [String : Int]()
 4     
 5     func collect(node_: TreeNode?) -> String {
 6         guard let node = node_ else { return "#" }
 7         
 8         let serial = "\(node.val),\(collect(node_: node.left)),\(collect(node_: node.right))"
 9         
10         if let count = subTrees[serial] {
11             subTrees[serial] = count + 1
12             if count + 1 == 2 {
13                 ans.append(node)
14             }
15         } else {
16             subTrees[serial] = 1
17         }
18         return serial
19         
20     }
21     
22     
23     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
24         collect(node_: root)
25         return ans
26     }
27 }

0287. Find the Duplicate Number (M)

Find the Duplicate Number (M)

题目

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(\(n^2\)).
There is only one duplicate number in the array, but it could be repeated more than once.

题意

思路

链表循环查找：参考官方解答

二分查找：参考 [LeetCode] 287. Find the Duplicate Number 寻找重复数

代码实现

Java

链表循环

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        fast = nums[0];
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

二分查找

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

250. Count Univalue Subtrees - Medium

Given a binary tree,count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

Example :

Input:  root = [5,1,5,null,5]

              5
             /             1   5
           / \             5   5   5

Output: 4

两次recursion，如果root是univalue的，返回1+ left + right，如果不是，返回left + right（有大量重复check，慢）

time: O(n^2),space: O(height)

/**
 * DeFinition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public int countUnivalSubtrees(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(unival(root)) {
            return 1 + countUnivalSubtrees(root.left) + countUnivalSubtrees(root.right);
        }
        return countUnivalSubtrees(root.left) + countUnivalSubtrees(root.right);
    }
    
    public boolean unival(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.left == null && root.right == null) {
            return true;
        }
        if(root.left != null && root.val != root.left.val) {
            return false;
        }
        if(root.right != null && root.val != root.right.val) {
            return false;
        }
        
        return unival(root.left) && unival(root.right);
    }
}

optimized: one pass

time: O(n),space: O(height)

/**
 * DeFinition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int cnt = 0;
    
    public int countUnivalSubtrees(TreeNode root) {
        unival(root);
        return cnt;
    }
    
    public boolean unival(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean left = unival(root.left);
        boolean right = unival(root.right);
        
        if(left && right) {
            if(root.left != null && root.val != root.left.val) {
                return false;
            }
            if(root.right != null && root.val != root.right.val) {
                return false;
            }
            cnt++;
            return true;
        }
        return false;
    }
}

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note: