Количество способов разделить двоичное дерево на две половины

Опубликовано: 23 Января, 2022

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

 Вход: 
          1 
        /  
      -1 -1 
                
                1 
Выход: 1
Единственный способ сделать это - удалить край справа от корня.
После этого у нас получится 2 поддерева с суммой = 0.
   1 
  /
-1

а также 

-1
  
   1
будет два поддерева.

Вход:
          1 
        /  
      -1 -1 
                
                -1 
Выход: 2

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простым решением будет удаление всех ребер дерева по одному и проверка, разбивает ли это дерево на две половины с одинаковой суммой. Если это так, мы увеличим окончательный ответ на 1. Это займет время O (N ² ) в худшем случае, когда «N» - количество узлов в дереве.
Эффективный подход:

Создайте переменную sum и сохраните в ней сумму всех элементов двоичного дерева. Мы можем найти сумму всех элементов двоичного дерева за время O (N), как описано в этой статье.
Теперь мы рекурсивно выполняем следующие шаги, начиная с корневого узла:
- Найдите сумму всех элементов его правого поддерева («R»). Если он равен половине общей суммы, мы увеличиваем счет на 1. Это связано с тем, что удаление ребра, соединяющего текущий узел с его правым дочерним элементом, разделит дерево на два дерева с равной суммой.
- Найдите сумму всех элементов его левого поддерева («L»). Если он равен половине общей суммы, мы увеличиваем счет на 1.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of a binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function to find the sum of
// all the nodes of BST
int findSum(node* curr)
{
    // If current node is
    // null
    if (curr == NULL)
        return 0;
 
    // Else
    return curr->data + findSum(curr->left)
           + findSum(curr->right);
}
 
// Function to recursively check
// if removing any edge divides tree into
// two halves
int checkSum(node* curr, int sum, int& ans)
{
    // Variable to store the
    // sum from left and right
    // child
    int l = 0, r = 0;
 
    // Checking sum from left sub-tree
    // if its not null
    if (curr->left != NULL) {
        l = checkSum(curr->left, sum, ans);
        if (2 * l == sum)
            ans++;
    }
 
    // Checking sum from right sub-tree
    // if its not null
    if (curr->right != NULL) {
        r = checkSum(curr->right, sum, ans);
        if (2 * r == sum)
            ans++;
    }
 
    // Finding the sum of all the elements
    // of current node
    return l + r + curr->data;
}
 
// Function to return the number
// of ways to remove an edge
int cntWays(node* root)
{
    // If root is null
    if (root == NULL)
        return 0;
 
    // To store the final answer
    int ans = 0;
 
    // Sum of all the elements of BST
    int sum = findSum(root);
 
    // If sum is odd then it won"t be possible
    // to break it into two halves
    if (sum % 2 == 1)
        return 0;
 
    // Calling the checkSum function
    checkSum(root, sum, ans);
 
    // Returning the final answer
    return ans;
}
 
// Driver code
int main()
{
    node* root = new node(1);
    root->left = new node(-1);
    root->right = new node(-1);
    root->right->right = new node(1);
 
    // Print the count of possible ways
    cout << cntWays(root);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Node of a binary tree
static class node
{
    int data;
    node left;
    node right;
    node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
static int ans;
 
// Function to find the sum of
// all the nodes of BST
static int findSum(node curr)
{
    // If current node is
    // null
    if (curr == null)
        return 0;
 
    // Else
    return curr.data + findSum(curr.left) +
                       findSum(curr.right);
}
 
// Function to recursively check
// if removing any edge divides tree
// into two halves
static int checkSum(node curr, int sum)
{
    // Variable to store the
    // sum from left and right
    // child
    int l = 0, r = 0;
 
    // Checking sum from left sub-tree
    // if its not null
    if (curr.left != null)
    {
        l = checkSum(curr.left, sum);
        if (2 * l == sum)
            ans++;
    }
 
    // Checking sum from right sub-tree
    // if its not null
    if (curr.right != null)
    {
        r = checkSum(curr.right, sum);
        if (2 * r == sum)
            ans++;
    }
 
    // Finding the sum of all the elements
    // of current node
    return l + r + curr.data;
}
 
// Function to return the number
// of ways to remove an edge
static int cntWays(node root)
{
    // If root is null
    if (root == null)
        return 0;
 
    // To store the final answer
    ans = 0;
 
    // Sum of all the elements of BST
    int sum = findSum(root);
 
    // If sum is odd then it won"t be possible
    // to break it into two halves
    if (sum % 2 == 1)
        return 0;
 
    // Calling the checkSum function
    checkSum(root, sum);
 
    // Returning the final answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    node root = new node(1);
    root.left = new node(-1);
    root.right = new node(-1);
    root.right.right = new node(1);
 
    // Print the count of possible ways
    System.out.print(cntWays(root));
}
}
 
// This code is contributed by PrinciRaj1992

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Node of a binary tree
public class node
{
    public int data;
    public node left;
    public node right;
    public node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
static int ans;
 
// Function to find the sum of
// all the nodes of BST
static int findSum(node curr)
{
    // If current node is
    // null
    if (curr == null)
        return 0;
 
    // Else
    return curr.data + findSum(curr.left) +
                       findSum(curr.right);
}
 
// Function to recursively check
// if removing any edge divides tree
// into two halves
static int checkSum(node curr, int sum)
{
    // Variable to store the
    // sum from left and right
    // child
    int l = 0, r = 0;
 
    // Checking sum from left sub-tree
    // if its not null
    if (curr.left != null)
    {
        l = checkSum(curr.left, sum);
        if (2 * l == sum)
            ans++;
    }
 
    // Checking sum from right sub-tree
    // if its not null
    if (curr.right != null)
    {
        r = checkSum(curr.right, sum);
        if (2 * r == sum)
            ans++;
    }
 
    // Finding the sum of all the elements
    // of current node
    return l + r + curr.data;
}
 
// Function to return the number
// of ways to remove an edge
static int cntWays(node root)
{
    // If root is null
    if (root == null)
        return 0;
 
    // To store the final answer
    ans = 0;
 
    // Sum of all the elements of BST
    int sum = findSum(root);
 
    // If sum is odd then it won"t be possible
    // to break it into two halves
    if (sum % 2 == 1)
        return 0;
 
    // Calling the checkSum function
    checkSum(root, sum);
 
    // Returning the final answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    node root = new node(1);
    root.left = new node(-1);
    root.right = new node(-1);
    root.right.right = new node(1);
 
    // Print the count of possible ways
    Console.Write(cntWays(root));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// javascript implementation of the approach   
// Node of a binary tree
class node {
    constructor(val) {
        this.data = val;
        this.prev = null;
        this.next = null;
    }
}
 
    var ans;
 
    // Function to find the sum of
    // all the nodes of BST
    function findSum( curr) {
        // If current node is
        // null
        if (curr == null)
            return 0;
 
        // Else
        return curr.data + findSum(curr.left) + findSum(curr.right);
    }
 
    // Function to recursively check
    // if removing any edge divides tree
    // into two halves
    function checkSum( curr , sum) {
        // Variable to store the
        // sum from left and right
        // child
        var l = 0, r = 0;
 
        // Checking sum from left sub-tree
        // if its not null
        if (curr.left != null) {
            l = checkSum(curr.left, sum);
            if (2 * l == sum)
                ans++;
        }
 
        // Checking sum from right sub-tree
        // if its not null
        if (curr.right != null) {
            r = checkSum(curr.right, sum);
            if (2 * r == sum)
                ans++;
        }
 
        // Finding the sum of all the elements
        // of current node
        return l + r + curr.data;
    }
 
    // Function to return the number
    // of ways to remove an edge
    function cntWays( root) {
        // If root is null
        if (root == null)
            return 0;
 
        // To store the final answer
        ans = 0;
 
        // Sum of all the elements of BST
        var sum = findSum(root);
 
        // If sum is odd then it won"t be possible
        // to break it into two halves
        if (sum % 2 == 1)
            return 0;
 
        // Calling the checkSum function
        checkSum(root, sum);
 
        // Returning the final answer
        return ans;
    }
 
    // Driver code
     
         root = new node(1);
        root.left = new node(-1);
        root.right = new node(-1);
        root.right.right = new node(1);
 
        // Prvar the count of possible ways
        document.write(cntWays(root));
 
// This code contributed by Rajput-Ji
</script>

Output:

Структуры данных

Количество способов разделить двоичное дерево на две половины

C++

Java

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ