663. Equal Tree Partition

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

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

Example

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

Output: true

C# solution

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

auto-draft, review before submit

#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

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

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

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

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

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

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

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

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

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

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.