663. Equal Tree Partition

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

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

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

Exemple

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

Output: true

C# solution

correspondant/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++ solution

brouillon automatique, à relire avant soumission

#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 solution

correspondant/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 solution

correspondant/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 solution

correspondant/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

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

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

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

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

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

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

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.