Рубрики

Поддерево с заданной суммой в двоичном дереве

Вам дано двоичное дерево и заданная сумма. Задача состоит в том, чтобы проверить, существует ли поддерево, сумма всех узлов которого равна заданной сумме.


Примеры :

// For above tree
Input : sum = 17
Output: "Yes"
// sum of all nodes of subtree {3, 5, 9} = 17

Input : sum = 11
Output: "No"
// no subtree with given sum exist

Идея состоит в том, чтобы пройтись по дереву способом Postorder, потому что здесь мы должны думать снизу вверх. Сначала вычислите сумму левого поддерева, затем правого поддерева и проверьте, удовлетворяет ли sum_left + sum_right + cur_node = sum условию, которое означает, что существует любое поддерево с данной суммой. Ниже приведена рекурсивная реализация алгоритма.

C ++

// C ++ программа для поиска поддерева с
// заданная сумма
#include<bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct Node

{

    int data;

    struct Node* left, *right;

};

  
/ * утилита, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

struct Node* newnode(int data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = node->right  = NULL;

    return (node);

}

  
// функция для проверки существования поддерева с заданной суммой
// cur_sum -> сумма текущего поддерева из ptr как root
// sum_left -> сумма левого поддерева из ptr как корня
// sum_right -> сумма правого поддерева из ptr как root

bool sumSubtreeUtil(struct Node *ptr, int *cur_sum, int sum)

{

    // базовое условие

    if (ptr == NULL)

    {

        *cur_sum = 0;

        return false;

    }

  

    // Здесь сначала идем в левое поддерево, затем в правое поддерево

    // затем сначала вычисляем сумму всех узлов поддерева

    // имея ptr как root и назначить его как cur_sum

    // cur_sum = sum_left + sum_right + ptr-> data

    // после этого мы проверяем, если cur_sum == сумма

    int sum_left = 0, sum_right = 0;

    return ( sumSubtreeUtil(ptr->left, &sum_left, sum) ||

             sumSubtreeUtil(ptr->right, &sum_right, sum) ||

        ((*cur_sum = sum_left + sum_right + ptr->data) == sum));

}

  
// Обертка над sumSubtreeUtil ()

bool sumSubtree(struct Node *root, int sum)

{

    // Инициализируем сумму поддерева с корнем

    int cur_sum = 0;

  

    return sumSubtreeUtil(root, &cur_sum, sum);

}

  
// программа для запуска дела

int main()

{

    struct Node *root = newnode(8);

    root->left    = newnode(5);

    root->right   = newnode(4);

    root->left->left = newnode(9);

    root->left->right = newnode(7);

    root->left->right->left = newnode(1);

    root->left->right->right = newnode(12);

    root->left->right->right->right = newnode(2);

    root->right->right = newnode(11);

    root->right->right->left = newnode(3);

    int sum = 22;

  

    if (sumSubtree(root, sum))

        cout << "Yes";

    else

        cout << "No";

    return 0;

}

Джава

// Java-программа, чтобы найти, если есть
// поддерево с заданной суммой

import java.util.*; 

class GFG

{

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

static class Node 

    int data; 

    Node left, right; 

}

  

static class INT

{

    int v;

    INT(int a)

    {

        v = a;

    }

}

  
/ * утилита, которая выделяет новый

 узел с заданными данными и

 нулевые левый и правый указатели. * /

static Node newnode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return (node); 

  
// функция для проверки существования
// любое поддерево с заданной суммой
// cur_sum -. сумма текущего поддерева
// из ptr как root
// sum_left -. сумма левого поддерева
// из ptr как root
// sum_right -. сумма правильного поддерева
// из ptr как root

static boolean sumSubtreeUtil(Node ptr, 

                              INT cur_sum, 

                              int sum) 

    // базовое условие

    if (ptr == null

    

        cur_sum = new INT(0); 

        return false

    

  

    // Здесь сначала мы идем налево

    // поддерево, затем правое поддерево

    // затем сначала вычисляем сумму

    // всех узлов поддерева, имеющих

    // ptr как root и назначаем его как

    // cur_sum. (cur_sum = sum_left +

    // sum_right + ptr.data) после этого

    // мы проверяем, если cur_sum == сумма

    INT sum_left = new INT(0), 

        sum_right = new INT(0); 

    return (sumSubtreeUtil(ptr.left, sum_left, sum) || 

            sumSubtreeUtil(ptr.right, sum_right, sum) || 

        ((cur_sum.v = sum_left.v + 

                      sum_right.v + ptr.data) == sum)); 

  
// Обертка над sumSubtreeUtil ()

static boolean sumSubtree(Node root, int sum) 

    // Инициализируем сумму

    // поддерево с корнем

    INT cur_sum = new INT( 0); 

  

    return sumSubtreeUtil(root, cur_sum, sum); 

  
// Код драйвера

public static void main(String args[])

    Node root = newnode(8); 

    root.left = newnode(5); 

    root.right = newnode(4); 

    root.left.left = newnode(9); 

    root.left.right = newnode(7); 

    root.left.right.left = newnode(1); 

    root.left.right.right = newnode(12); 

    root.left.right.right.right = newnode(2); 

    root.right.right = newnode(11); 

    root.right.right.left = newnode(3); 

    int sum = 22

  

    if (sumSubtree(root, sum)) 

        System.out.println( "Yes"); 

    else

        System.out.println( "No"); 


}

  
// Этот код добавлен
// Арнаб Кунду

python3

# Python3 программа, чтобы найти, если есть
# поддерево с заданной суммой

  
# Узел двоичного дерева
"" "утилита, которая выделяет новый узел
с заданным ключом "" "

class newnode: 

  

    # Конструкция для создания нового узла

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# функция для проверки существования
# поддерево с заданной суммой
# cur_sum -. сумма текущего поддерева
# из ptr как root
# sum_left -. сумма левого поддерева от
# ptr от имени пользователя root
# sum_right -. сумма правильного поддерева
# из ptr как root

def sumSubtreeUtil(ptr,cur_sum,sum): 

  

    # базовое состояние

    if (ptr == None):

        cur_sum[0] = 0

        return False

  

    # Здесь сначала мы идем в левое поддерево,

    # тогда правое поддерево потом сначала мы

    # вычислить сумму всех узлов поддерева

    # имея ptr как root и назначить его как cur_sum

    # cur_sum = sum_left + sum_right + ptr.data

    # после этого мы проверяем, если cur_sum == сумма

    sum_left, sum_right = [0], [0]

    x=sumSubtreeUtil(ptr.left, sum_left, sum)

    y=sumSubtreeUtil(ptr.right, sum_right, sum)

    cur_sum[0] = (sum_left[0] + 

                  sum_right[0] + ptr.data)

    return ((x or y)or (cur_sum[0] == sum))

  
# Обертка над sumSubtreeUtil ()

def sumSubtree(root, sum): 

  

    # Инициализировать сумму поддерева с корнем

    cur_sum = [0

  

    return sumSubtreeUtil(root, cur_sum, sum

  
Код водителя

if __name__ == '__main__':

  

    root = newnode(8

    root.left = newnode(5

    root.right = newnode(4

    root.left.left = newnode(9

    root.left.right = newnode(7

    root.left.right.left = newnode(1

    root.left.right.right = newnode(12

    root.left.right.right.right = newnode(2

    root.right.right = newnode(11

    root.right.right.left = newnode(3

    sum = 22

  

    if (sumSubtree(root, sum)) :

        print("Yes" )

    else:

        print("No")

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

using System;

  
// C # программа, чтобы найти, если есть
// поддерево с заданной суммой

public class GFG

{

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

public class Node

{

    public int data;

    public Node left, right;

}

  

public class INT

{

    public int v;

    public INT(int a)

    {

        v = a;

    }

}

  
/ * утилита, которая выделяет новый
узел с заданными данными и
нулевые левый и правый указатели. * /

public static Node newnode(int data)

{

    Node node = new Node();

    node.data = data;

    node.left = node.right = null;

    return (node);

}

  
// функция для проверки существования
// любое поддерево с заданной суммой
// cur_sum -. сумма текущего поддерева
// из ptr как root
// sum_left -. сумма левого поддерева
// из ptr как root
// sum_right -. сумма правильного поддерева
// из ptr как root

public static bool sumSubtreeUtil(Node ptr, INT cur_sum, int sum)

{

    // базовое условие

    if (ptr == null)

    {

        cur_sum = new INT(0);

        return false;

    }

  

    // Здесь сначала мы идем налево

    // поддерево, затем правое поддерево

    // затем сначала вычисляем сумму

    // всех узлов поддерева, имеющих

    // ptr как root и назначаем его как

    // cur_sum. (cur_sum = sum_left +

    // sum_right + ptr.data) после этого

    // мы проверяем, если cur_sum == сумма

    INT sum_left = new INT(0), sum_right = new INT(0);

    return (sumSubtreeUtil(ptr.left, sum_left, sum) 

            || sumSubtreeUtil(ptr.right, sum_right, sum) 

            || ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum));

}

  
// Обертка над sumSubtreeUtil ()

public static bool sumSubtree(Node root, int sum)

{

    // Инициализируем сумму

    // поддерево с корнем

    INT cur_sum = new INT(0);

  

    return sumSubtreeUtil(root, cur_sum, sum);

}

  
// Код драйвера

public static void Main(string[] args)

{

    Node root = newnode(8);

    root.left = newnode(5);

    root.right = newnode(4);

    root.left.left = newnode(9);

    root.left.right = newnode(7);

    root.left.right.left = newnode(1);

    root.left.right.right = newnode(12);

    root.left.right.right.right = newnode(2);

    root.right.right = newnode(11);

    root.right.right.left = newnode(3);

    int sum = 22;

  

    if (sumSubtree(root, sum))

    {

        Console.WriteLine("Yes");

    }

    else

    {

        Console.WriteLine("No");

    }

}
}

  
// Этот код предоставлен Shrikant13


Выход:

Yes

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поддерево с заданной суммой в двоичном дереве

0.00 (0%) 0 votes