План курса / Все задачи / Алгоритмы и структуры данных

Эквивалентные поддеревья

средне

Дан корень бинарного дерева root, в каждой вершине которого записана одна буква A–Z.

Нужно найти две вершины, поддеревья которых содержат одинаковое множество букв (без учёта частот) и при этом сумма количества вершин в этих двух поддеревьях максимальна.

Верните корни найденных поддеревьев.

Пример 1:

Ввод: root = [A,B,E,D,E,B,null,F,null,null,null,D,F]
Вывод: [B,E] или [E,B]
Объяснение: порядок вывода не имеет значения

Пример 2:

Ввод: root = [A,A,A,A]
Вывод: [A,A]
Объяснение: одна из вершин может находиться в поддереве другой

Пример 3:

Ввод: root = [A,B,C]
Вывод: [null,null]
Объяснение: если ответ не найден, то возвращаем два пустых указателя

Ограничения:

Число узлов в дереве >= 1
Высота дерева <= 1000

/**
 * public class TreeNode {
 *     public char val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(char val, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    // Поля для хранения состояния между вызовами Dfs
    private static Dictionary<int, (TreeNode node, int size)> best;
    private static List<TreeNode?> result;
    private static int bestSum;

    /// Находит два поддерева с одинаковым множеством букв (без учёта частот)
    /// и максимальной суммой количества узлов.
    /// Эквивалентность: множества букв совпадают, порядок и количество вхождений не важны.
    public static List<TreeNode> FindSubtrees(TreeNode root) {
        best = new Dictionary<int, (TreeNode node, int size)>();
        result = new List<TreeNode?> { null, null };
        bestSum = -1;

        Dfs(root);
        return result;
    }

    /// Преобразует букву в индекс (A=0, B=1, ...).
    /// Работает только для заглавных латинских букв.
    private static int GetLetterIndex(char val) {
        int code = val - 'A';
        return (code >= 0 && code < 26) ? code : 0;
    }

    /// Рекурсивный обход дерева.
    /// Возвращает:
    /// mask — битовую маску всех букв в поддереве
    /// size — количество узлов в поддереве
    private static (int mask, int size) Dfs(TreeNode? node) {
        if (node == null)
            return (0, 0);

        // Рекурсивно получаем маски и размеры левого и правого поддеревьев
        var (leftMask, leftSize) = Dfs(node.left);
        var (rightMask, rightSize) = Dfs(node.right);

        // Формируем битовую маску для текущего узла:
        // Каждая буква A-Z соответствует одному биту (A=0, B=1, C=2, ...)
        int mask = leftMask | rightMask | (1 << GetLetterIndex(node.val));

        // Размер текущего поддерева
        int size = leftSize + rightSize + 1;

        // Если уже встречалось поддерево с такой маской
        if (best.TryGetValue(mask, out var other)) {
            int totalSize = size + other.size;
            if (totalSize > bestSum) {
                bestSum = totalSize;
                result[0] = other.node; // сохранённое ранее поддерево
                result[1] = node;       // текущее поддерево
            }
        }

        // Сохраняем это поддерево, если оно самое большое для этой маски
        if (!best.ContainsKey(mask) || size > best[mask].size) {
            best[mask] = (node, size);
        }
        return (mask, size);
    }
}

#include <vector>

using namespace std;

/**
 * struct TreeNode {
 *     char val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

using namespace std;

/**
 * Находит два поддерева с одинаковым множеством букв (без учёта порядка и частот)
 * и максимальной суммой количества узлов.
 */
vector<TreeNode*> findSubtrees(TreeNode* root) {
    // best: маска -> (указатель на корень поддерева, размер поддерева)
    unordered_map<int, pair<TreeNode*, int>> best;

    // Результат: два найденных поддерева
    vector<TreeNode*> result(2, nullptr);

    // Лучшая найденная сумма размеров поддеревьев
    int bestSum = -1;

    // DFS — рекурсивный обход дерева
    function<pair<int, int>(TreeNode*)> dfs = [&](TreeNode* node) -> pair<int, int> {
        // Возвращает:
        //    mask — битовая маска всех букв в поддереве
        //    size — размер поддерева
        if (!node) return {0, 0};

        // Получаем маски и размеры для левого и правого поддеревьев
        auto [leftMask, leftSize] = dfs(node->left);
        auto [rightMask, rightSize] = dfs(node->right);

        // Битовая маска для текущего узла:
        // Каждая буква A-Z соответствует одному биту (A=0, B=1, C=2 и т.д.)
        int currMask = leftMask | rightMask | (1 << (node->val - 'A'));

        // Размер текущего поддерева
        int size = leftSize + rightSize + 1;

        // Если уже встречалось поддерево с такой же маской, проверяем суммарный размер
        auto it = best.find(currMask);
        if (it != best.end()) {
            int total = size + it->second.second;
            if (total > bestSum) {
                bestSum = total;
                result[0] = it->second.first; // сохранённое ранее поддерево
                result[1] = node;             // текущее поддерево
            }
        }

        // Сохраняем это поддерево, если оно больше предыдущего для этой маски
        if (it == best.end() || size > it->second.second) {
            best[currMask] = {node, size};
        }

        return {currMask, size};
    };

    dfs(root);
    return result;
}

package main

/**
 * type TreeNode struct {
 *     Val   rune
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func findSubtrees(root *TreeNode) []*TreeNode {
    // ключ: битовая маска, значение: (узел, размер поддерева)
    best := make(map[int]struct {
        node *TreeNode
        size int
    })

    // результат: два найденных поддерева
    result := []*TreeNode{nil, nil}
    // лучшая найденная сумма размеров поддеревьев
    resultSum := -1
    // letterMask — преобразует символ в битовую маску
    letterMask := func(ch rune) int {
        return 1 << (int(ch) - int('A'))
    }

    // dfs — рекурсивно обходит дерево
    var dfs func(node *TreeNode) (_mask int, _size int)
    dfs = func(node *TreeNode) (int, int) {
        // Возвращает:
        //    mask — битовая маска всех букв в поддереве
        //    size — размер поддерева
        if node == nil {
            return 0, 0
        }

        // Рекурсивно получаем маски и размеры поддеревьев
        leftMask, leftSize := dfs(node.Left)
        rightMask, rightSize := dfs(node.Right)

        // Маска и размер для текущего узла
        currMask := leftMask | rightMask | letterMask(node.Val)
        size := leftSize + rightSize + 1

        // Проверяем, встречалось ли уже такое множество букв
        if other, ok := best[currMask]; ok {
            totalSize := size + other.size
            if totalSize > resultSum {
                resultSum = totalSize
                result[0] = other.node
                result[1] = node
            }
        }

        // Сохраняем это поддерево, если оно больше предыдущего для этой маски
        if other, ok := best[currMask]; !ok || size > other.size {
            best[currMask] = struct {
                node *TreeNode
                size int
            }{node, size}
        }
        return currMask, size
    }

    dfs(root)
    return result
}

import java.util.*;

/**
 * class TreeNode {
 *     Character val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(Character val) { this.val = val; }
 *     TreeNode(Character val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    // ключ: битовая маска -> (узел, размер поддерева)
    private Map<Integer, AbstractMap.SimpleEntry<TreeNode, Integer>> best;

    // результат: два найденных поддерева
    private List<TreeNode> result;

    // лучшая найденная сумма размеров поддеревьев
    private int resultSum;

    /**
     * DFS по дереву.
     * @param node текущий узел
     * @return массив [mask, size]:
     *         mask — битовая маска всех букв в поддереве
     *         size — количество узлов в поддереве
     */
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        // Рекурсивно получаем маски и размеры поддеревьев
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Маска и размер для текущего узла
        int currMask = left[0] | right[0] | letterMask(node.val);
        int size = left[1] + right[1] + 1;

        // Проверяем, встречалось ли уже такое множество букв
        if (best.containsKey(currMask)) {
            var other = best.get(currMask);
            int totalSize = size + other.getValue();
            if (totalSize > resultSum) {
                resultSum = totalSize;
                result.set(0, other.getKey());
                result.set(1, node);
            }
        }

        // Сохраняем это поддерево, если оно больше предыдущего для этой маски
        if (!best.containsKey(currMask) || size > best.get(currMask).getValue()) {
            best.put(currMask, new AbstractMap.SimpleEntry<>(node, size));
        }

        return new int[]{currMask, size};
    }

    /**
     * Преобразует символ в битовую маску.
     * Каждой букве A-Z соответствует один бит.
     */
    private int letterMask(char ch) {
        return 1 << (ch - 'A');
    }

    public List<TreeNode> findSubtrees(TreeNode root) {
        best = new HashMap<>();
        result = new ArrayList<>(Arrays.asList(null, null));
        resultSum = -1;

        dfs(root);
        return result;
    }
}

from typing import List, Optional, Tuple, Dict
from tree_node import TreeNode

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

def find_subtrees(root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
    # ключ: битовая маска, значение: узел дерева с такой битовой маской
    # и число вершин в поддереве
    best: Dict[int, Tuple[TreeNode, int]] = {}
    
    # результат: два найденных поддерева
    result: List[Optional[TreeNode]] = [None, None]
    
    # лучшая найденная сумма размеров поддеревьев
    result_sum = -1  

    def letter_mask(ch: str) -> int:
        """Преобразует символ в битовую маску."""
        return 1 << (ord(ch) - ord('A'))

    def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
        """
        Возвращает:
            mask — битовая маска всех букв в поддереве
            size — размер поддерева
        """
        nonlocal result_sum, result

        if not node:
            return 0, 0

        # Рекурсивно получаем маски и размеры поддеревьев
        left_mask, left_size = dfs(node.left)
        right_mask, right_size = dfs(node.right)

        # Маска и размер для текущего узла
        curr_mask = left_mask | right_mask | letter_mask(node.val)
        size = left_size + right_size + 1

        # Проверяем, встречалось ли уже такое множество букв
        if curr_mask in best:
            other_node, other_size = best[curr_mask]
            total_size = size + other_size

            # Обновляем лучший результат, если нашли больше
            if total_size > result_sum:
                result_sum = total_size
                result = [other_node, node]

        # Сохраняем это поддерево, если оно больше предыдущего для этой маски
        if curr_mask not in best or size > best[curr_mask][1]:
            best[curr_mask] = (node, size)
        return curr_mask, size

    dfs(root)
    return result

import { TreeNode } from './treeNode.js';

/**
 * class TreeNode {
 *     constructor(val, left, right) {
 *         this.val = val;
 *         this.left = (left === undefined ? null : left);
 *         this.right = (right === undefined ? null : right);
 *     }
 * }
 */

/**
 * Преобразует значение узла в индекс буквы (A=0, B=1, ...).
 * Работает для строки, символа или числа. Любое другое значение → 0.
 * @param {*} val
 * @returns {number}
 */
function getLetterIndex(val) {
    if (val == null) return 0;
    const str = String(val);
    if (!str.length) return 0;

    const code = str.charCodeAt(0); // код первого символа
    // Допускаем только заглавные буквы латиницы A-Z
    if (code < 65 || code > 90) return 0;

    return code - 65;
}

/**
 * Находит два поддерева с одинаковым множеством букв (без учёта частот)
 * и максимальной суммой количества узлов.
 *
 * Эквивалентность: у двух поддеревьев совпадают множества букв.
 * Порядок и количество вхождений букв не имеют значения.
 *
 * @param {TreeNode|null} root Корень исходного дерева
 * @returns {[TreeNode|null, TreeNode|null]} Массив из двух найденных поддеревьев или [null, null]
 */
export function findSubtrees(root) {
    /** @type {Map<number, [TreeNode, number]>} */
    const best = new Map(); // mask -> [node, size]
    /** @type {[TreeNode|null, TreeNode|null]} */
    const result = [null, null];
    let bestSum = -1; // Лучшая найденная сумма размеров двух поддеревьев

    /**
     * DFS — рекурсивно обходит дерево и возвращает:
     * @param {TreeNode|null} node
     * @returns {[number, number]} [mask, size]
     * mask — битовая маска всех букв в поддереве
     * size — количество узлов в поддереве
     */
    function dfs(node) {
        if (!node) return [0, 0];

        // Рекурсивно получаем маски и размеры левого и правого поддеревьев
        const [leftMask, leftSize] = dfs(node.left);
        const [rightMask, rightSize] = dfs(node.right);

        // Формируем битовую маску для текущего узла
        const mask = leftMask | rightMask | (1 << getLetterIndex(node.val));

        // Размер поддерева
        const size = leftSize + rightSize + 1;

        // Если уже встречалось поддерево с такой маской
        if (best.has(mask)) {
            const [otherNode, otherSize] = best.get(mask);
            const totalSize = size + otherSize;

            // Обновляем лучший результат
            if (totalSize > bestSum) {
                bestSum = totalSize;
                result[0] = otherNode;
                result[1] = node;
            }
        }

        // Сохраняем это поддерево, если оно самое большое для этой маски
        if (!best.has(mask) || size > best.get(mask)[1]) {
            best.set(mask, [node, size]);
        }

        return [mask, size];
    }

    dfs(root);
    return result;
}

Оценка сложности

Время: O(n), где n - число вершин в дереве
Память: O(n)

Идея решения

Мы ищем два поддерева, в которых набор букв одинаковый. Чтобы не сравнивать эти наборы медленно, мы кодируем их в битовую маску. У каждой буквы свой бит в числе (A — первый бит, B — второй, C — третий и т.д.). Например:

A → 0001
B → 0010
С → 0100
A, C → 0101

Так мы превращаем любое множество букв в одно число и если у двух поддеревьев числа одинаковые — значит, у них и набор букв одинаковый.

Подход с битовыми масками возможен только когда набор различных букв маленький. У нас это 26 (A-Z) и int32 хватит, чтобы закодировать каждую букву, но если набор будет >32 буквы, то int32 уже не подходит.

Сравнивать числа очень быстро, поэтому алгоритм работает эффективно.

Итог: мы обходим дерево DFS‑ом, для каждого узла считаем его маску и размер. Если такую маску уже встречали — проверяем, не получилось ли у нас пара поддеревьев с большей суммой размеров и при необходимости обновляем ответ.