Рубрики

Сумма пути от корня к листу равна заданному числу

Если дано двоичное дерево и число, верните true, если у дерева есть путь от корня к листу, так что сложение всех значений вдоль пути равняется данному числу. Вернуть false, если такой путь не найден.

Например, в приведенном выше пути от корня к листу существуют следующие суммы.

21 -> 10 — 8 — 3
23 -> 10 — 8 — 5
14 -> 10 — 2 — 2

Поэтому возвращаемое значение должно быть истинным только для чисел 21, 23 и 14. Для любого другого числа возвращаемое значение должно быть ложным.

Алгоритм:
Рекурсивно проверять, есть ли у левого или правого дочернего элемента сумма пути, равная (число — значение в текущем узле)

Реализация:

C ++

#include <bits/stdc++.h>

using namespace std;

#define bool int 

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

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

  
Стратегия: вычтите значение узла из суммы при повторении вниз,
и проверьте, равна ли сумма 0, когда вы исчерпали дерево.
* /

bool hasPathSum(node* Node, int sum) 

    / * вернуть true, если у нас кончится дерево и сумма == 0 * /

    if (Node == NULL) 

    

        return (sum == 0); 

    

      

    else

    

        bool ans = 0; 

      

        / * в противном случае проверьте оба поддерева * /

        int subSum = sum - Node->data; 

      

        / * Если мы достигнем конечного узла и сумма станет 0, тогда вернем true * /

        if ( subSum == 0 && Node->left == NULL && Node->right == NULL ) 

        return 1; 

      

        if(Node->left) 

            ans = ans || hasPathSum(Node->left, subSum); 

        if(Node->right) 

            ans = ans || hasPathSum(Node->right, subSum); 

      

        return ans; 

    

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

node* newnode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

      

    return(Node); 

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main() 

  

    int sum = 21; 

      

    / * Построенное двоичное дерево

                10

            / /

            8 2

        ///

        3 5 2

    * /

    node *root = newnode(10); 

    root->left = newnode(8); 

    root->right = newnode(2); 

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

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

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

      

    if(hasPathSum(root, sum)) 

        cout << "There is a root-to-leaf path with sum " << sum; 

    else

        cout << "There is no root-to-leaf path with sum " << sum; 

      

    return 0; 

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

С

#include<stdio.h>
#include<stdlib.h>
#define bool int

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

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

struct node

{

   int data;

   struct node* left;

   struct node* right;

};

  
/ *

 Если дано дерево и сумма, верните true, если есть путь от корня

 вниз до листа, так что складывая все значения вдоль пути

 равняется данной сумме.

  

 Стратегия: вычтите значение узла из суммы при повторении вниз,

 и проверьте, равна ли сумма 0, когда вы исчерпали дерево.

* /

bool hasPathSum(struct node* node, int sum)

{

  / * вернуть true, если у нас кончится дерево и сумма == 0 * /

  if (node == NULL)

  {

     return (sum == 0);

  }

   

  else

  {

    bool ans = 0;  

   

    / * в противном случае проверьте оба поддерева * /

    int subSum = sum - node->data;

   

    / * Если мы достигнем конечного узла и сумма станет 0, тогда вернем true * /

    if ( subSum == 0 && node->left == NULL && node->right == NULL )

      return 1;

   

    if(node->left)

      ans = ans || hasPathSum(node->left, subSum);

    if(node->right)

      ans = ans || hasPathSum(node->right, subSum);

   

    return ans;

  }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вспомогательная функция, которая выделяет новый узел с

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

struct node* newnode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  

  int sum = 21;

  

  / * Построенное двоичное дерево

            10

          / /

        8 2

      ///

    3 5 2

  * /

  struct node *root = newnode(10);

  root->left        = newnode(8);

  root->right       = newnode(2);

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

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

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

  

  if(hasPathSum(root, sum))

    printf("There is a root-to-leaf path with sum %d", sum);

  else

    printf("There is no root-to-leaf path with sum %d", sum);

  

  getchar();

  return 0;

}

Джава

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

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree {

   

    Node root;

       

    / *

     Если дано дерево и сумма, верните true, если есть путь от корня

     вниз до листа, так что складывая все значения вдоль пути

     равняется данной сумме.

    

     Стратегия: вычтите значение узла из суммы при повторении вниз,

     и проверьте, равна ли сумма 0, когда вы исчерпали дерево.

     * /

   

    boolean haspathSum(Node node, int sum) 

    {

        if (node == null)

            return (sum == 0);

        else 

        {

            boolean ans = false;

   

            / * в противном случае проверьте оба поддерева * /

            int subsum = sum - node.data;

            if (subsum == 0 && node.left == null && node.right == null)

                return true;

            if (node.left != null)

                ans = ans || haspathSum(node.left, subsum);

            if (node.right != null)

                ans = ans || haspathSum(node.right, subsum);

            return ans;

        }

    }

      

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[]) 

    {

        int sum = 21;

          

        / * Построенное двоичное дерево

              10

             / /

           8 2

          ///

         3 5 2

        * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.right = new Node(2);

        tree.root.left.left = new Node(3);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(2);

   

        if (tree.haspathSum(tree.root, sum))

            System.out.println("There is a root to leaf path with sum " + sum);

        else

            System.out.println("There is no root to leaf path with sum " + sum);

    }

}

   
// Этот код предоставлен Mayank Jaiswal (mayank_24)

питон

# Программа Python, чтобы найти, есть ли путь от корня до суммы

  
# Узел двоичного дерева

class Node:

  

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
«»»

 Если дано дерево и сумма, верните true, если есть путь от корня

 вниз до листа, так что складывая все значения вдоль пути

 равняется данной сумме.

   

 Стратегия: вычтите значение узла из суммы при повторении вниз,

 и проверьте, равна ли сумма 0, когда вы исчерпали дерево.

«»»
# s это сумма

def hasPathSum(node, s):

      

    # Вернуть true, если у нас кончится дерево и s = 0

    if node is None:

        return (s == 0)

  

    else:

        ans = 0 

          

        # В противном случае проверьте оба поддерева

        subSum = s - node.data 

          

        # Если мы достигнем конечного узла и сумма станет 0, то

        # вернуть True

        if(subSum == 0 and node.left == None and node.right == None):

            return True 

  

        if node.left is not None:

            ans = ans or hasPathSum(node.left, subSum)

        if node.right is not None:

            ans = ans or hasPathSum(node.right, subSum)

  

        return ans 

  
# Драйверная программа для проверки вышеуказанных функций

  

s = 21

root = Node(10)

root.left = Node(8)

root.right = Node(2)

root.left.right = Node(5)

root.left.left = Node(3)

root.right.left = Node(2)

  

if hasPathSum(root, s):

    print "There is a root-to-leaf path with sum %d" %(s)

else:

    print "There is no root-to-leaf path with sum %d" %(s)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  
/ *
Если дано дерево и сумма, верните true, если
есть путь от корня до
лист, такой, что сложение всех значений
вдоль пути равна заданной сумме.

  
Стратегия: вычтите значение узла из
сумма при повторении вниз, и проверьте, чтобы увидеть
если сумма равна 0, когда вы исчерпали дерево.
* /

  

public virtual bool haspathSum(Node node, 

                               int sum)

{

    if (node == null)

    {

        return (sum == 0);

    }

    else

    {

        bool ans = false;

  

        / * в противном случае проверьте оба поддерева * /

        int subsum = sum - node.data;

        if (subsum == 0 && node.left == null && 

                           node.right == null)

        {

            return true;

        }

        if (node.left != null)

        {

            ans = ans || haspathSum(node.left, subsum);

        }

        if (node.right != null)

        {

            ans = ans || haspathSum(node.right, subsum);

        }

        return ans;

    }

}

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

public static void Main(string[] args)

{

    int sum = 21;

  

    / * Построенное двоичное дерево

        10

        / /

    8 2

    ///

    3 5 2

    * /

    GFG tree = new GFG();

    tree.root = new Node(10);

    tree.root.left = new Node(8);

    tree.root.right = new Node(2);

    tree.root.left.left = new Node(3);

    tree.root.left.right = new Node(5);

    tree.root.right.left = new Node(2);

  

    if (tree.haspathSum(tree.root, sum))

    {

        Console.WriteLine("There is a root to leaf " +

                              "path with sum " + sum);

    }

    else

    {

        Console.WriteLine("There is no root to leaf "

                               "path with sum " + sum);

    }

}
}

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


Выход :

There is a root to leaf path with sum 21

Сложность времени : O (n)

Ссылки : http://cslibrary.stanford.edu/110/BinaryTrees.html

Автор: Тушар Рой

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы.

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

Сумма пути от корня к листу равна заданному числу

0.00 (0%) 0 votes