Задача: 663. Equal Tree Partition
Сложность: medium

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

Пример:

Input: root = [5,10,10,null,null,2,3]
Output: true

👨‍💻 Алгоритм:

1⃣Вычисление общей суммы:
Напишите функцию для вычисления общей суммы всех узлов дерева.

2⃣Проверка возможности разделения:
Напишите функцию, чтобы рекурсивно проверить, может ли поддерево быть равно половине общей суммы. Если такое поддерево найдено, значит дерево можно разделить на две части с равными суммами.

3⃣Валидация и возврат результата:
Проверьте, что общая сумма четная (так как только в этом случае возможно её разделение на две равные части), и используйте функцию проверки поддерева, чтобы определить, можно ли разделить дерево на две части с равными суммами.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool CheckEqualTree(TreeNode root) {
        int totalSum = SumTree(root);
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        return CheckSubtreeSum(root, target, root);
    }

    private int SumTree(TreeNode node) {
        if (node == null) return 0;
        return node.val + SumTree(node.left) + SumTree(node.right);
    }

    private bool CheckSubtreeSum(TreeNode node, int target, TreeNode root) {
        if (node == null) return false;
        if (node != root && SumTree(node) == target) {
            return true;
        }
        return CheckSubtreeSum(node.left, target, root) || CheckSubtreeSum(node.right, target, root);
    }
}

Ставь 👍 и забирай 📚 Базу знаний