663. Equal Tree Partition

LeetCode medium original: C# #backtracking #csharp #leetcode #medium #recursion #tree #two-pointers

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

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

Ejemplo

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

Output: true

C# solución

coincidente/original

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);
    }
}

C++ solución

borrador automático, revisar antes de enviar

#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 x) { val = x; }
}
class Solution {
public:
    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);
    }
}

Java solución

coincidente/original

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

class Solution {
    public boolean 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 boolean 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);
    }
}

JavaScript solución

coincidente/original

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

var checkEqualTree = function(root) {
    const totalSum = sumTree(root);
    if (totalSum % 2 !== 0) return false;
    const target = totalSum / 2;
    return checkSubtreeSum(root, target, root);
};

function sumTree(node) {
    if (!node) return 0;
    return node.val + sumTree(node.left) + sumTree(node.right);
}

function checkSubtreeSum(node, target, root) {
    if (!node) return false;
    if (node !== root && sumTree(node) === target) {
        return true;
    }
    return checkSubtreeSum(node.left, target, root) || checkSubtreeSum(node.right, target, root);
}

Go solución

coincidente/original

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

func checkEqualTree(root *TreeNode) bool {
    totalSum := sumTree(root)
    if totalSum%2 != 0 {
        return false
    }
    target := totalSum / 2
    return checkSubtreeSum(root, target, root)
}

func sumTree(node *TreeNode) int {
    if node == nil {
        return 0
    }
    return node.Val + sumTree(node.Left) + sumTree(node.Right)
}

func checkSubtreeSum(node *TreeNode, target int, root *TreeNode) bool {
    if node == nil {
        return false
    }
    if node != root && sumTree(node) == target {
        return true
    }
    return checkSubtreeSum(node.Left, target, root) || checkSubtreeSum(node.Right, target, root)
}

Algorithm

Вычисление общей суммы:

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

Проверка возможности разделения:

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

Валидация и возврат результата:

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.