663. Equal Tree Partition

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

Ví dụ

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

Output: true

C# lời giải

đã khớp/gốc

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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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

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

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

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

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

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

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.