652. Find Duplicate Subtrees

LeetCode medium original: C# #csharp #hash-table #leetcode #medium #search #string #tree #two-pointers

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

Если задан корень бинарного дерева, return все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов.

예제:

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

Output: [[2,4],[4]]

C# 해법

매칭됨/원본

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        List<TreeNode> result = new List<TreeNode>();
        Serialize(root, count, result);
        return result;
    }
    private string Serialize(TreeNode node, Dictionary<string, int> count, List<TreeNode> result) {
        if (node == null) return "#";
        string serial = node.val + "," + Serialize(node.left, count, result) + "," + Serialize(node.right, count, result);
        if (count.ContainsKey(serial)) {
            count[serial]++;
        } else {
            count[serial] = 1;
        }
        if (count[serial] == 2) {
            result.Add(node);
        }
        return serial;
    }
}

C++ 해법

자동 초안, 제출 전 검토

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        unordered_map<string, int> count = new unordered_map<string, int>();
        List<TreeNode> result = new List<TreeNode>();
        Serialize(root, count, result);
        return result;
    }
    private string Serialize(TreeNode node, unordered_map<string, int> count, List<TreeNode> result) {
        if (node == null) return "#";
        string serial = node.val + "," + Serialize(node.left, count, result) + "," + Serialize(node.right, count, result);
        if (count.count(serial)) {
            count[serial]++;
        } else {
            count[serial] = 1;
        }
        if (count[serial] == 2) {
            result.push_back(node);
        }
        return serial;
    }
}

Java 해법

매칭됨/원본

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, Integer> count = new HashMap<>();
        List<TreeNode> result = new ArrayList<>();
        serialize(root, count, result);
        return result;
    }

    private String serialize(TreeNode node, Map<String, Integer> count, List<TreeNode> result) {
        if (node == null) return "#";
        String serial = node.val + "," + serialize(node.left, count, result) + "," + serialize(node.right, count, result);
        count.put(serial, count.getOrDefault(serial, 0) + 1);
        if (count.get(serial) == 2) {
            result.add(node);
        }
        return serial;
    }
}

JavaScript 해법

매칭됨/원본

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var findDuplicateSubtrees = function(root) {
    const count = new Map();
    const result = [];
    
    const serialize = (node) => {
        if (!node) return "#";
        const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
        count.set(serial, (count.get(serial) || 0) + 1);
        if (count.get(serial) === 2) {
            result.push(node);
        }
        return serial;
    };
    
    serialize(root);
    return result;
};

Python 해법

매칭됨/원본

from collections import defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findDuplicateSubtrees(root):
    def serialize(node):
        if not node:
            return "#"
        serial = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
        count[serial] += 1
        if count[serial] == 2:
            result.append(node)
        return serial
    
    count = defaultdict(int)
    result = []
    serialize(root)
    return result

Go 해법

매칭됨/원본

package main

import (
    "fmt"
    "strconv"
    "strings"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    count := make(map[string]int)
    result := []*TreeNode{}
    serialize(root, count, &result)
    return result
}

func serialize(node *TreeNode, count map[string]int, result *[]*TreeNode) string {
    if node == nil {
        return "#"
    }
    serial := strconv.Itoa(node.Val) + "," + serialize(node.Left, count, result) + "," + serialize(node.Right, count, result)
    count[serial]++
    if count[serial] == 2 {
        *result = append(*result, node)
    }
    return serial
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 3, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 4}}}
    result := findDuplicateSubtrees(root)
    for _, node := range result {
        fmt.Println(node.Val)
    }
}

Algorithm

Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

find поддеревья, которые появляются более одного раза, и return корневые узлы этих поддеревьев.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.