Рубрики

Сумма всех чисел, которые сформированы от корневых до листовых путей

Дано бинарное дерево, где каждое значение узла является цифрой от 1 до 9. Найдите сумму всех чисел, которые формируются от корневых до конечных путей.

Например, рассмотрим следующее двоичное дерево.

           6
       /      \
     3          5
   /   \          \
  2     5          4  
      /   \
     7     4
  There are 4 leaves, hence 4 root to leaf paths:
   Path                    Number
  6->3->2                   632
  6->3->5->7               6357
  6->3->5->4               6354
  6->5>4                    654   
Answer = 632 + 6357 + 6354 + 654 = 13997 

Идея состоит в том, чтобы сделать предварительный обход дерева. При обходе предзаказа следите за значением, вычисленным до текущего узла, пусть это значение будет val . Для каждого узла мы обновляем val как val * 10 плюс данные узла.

C ++

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

using namespace std;

  

class node 

    public:

    int data; 

    node *left, *right; 

}; 

  
// функция для выделения нового узла с данными

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = Node->right = NULL; 

    return (Node); 

  
// Возвращает сумму всех путей от корня к листу.
// Первый параметр - root
// текущего поддерева, второе
// параметр - это значение сформированного числа
// по узлам от корня до этого узла

int treePathsSumUtil(node *root, int val) 

    // Базовый вариант

    if (root == NULL) return 0; 

  

    // Обновляем val

    val = (val*10 + root->data); 

  

    // если текущим узлом является лист, вернуть текущее значение val

    if (root->left==NULL && root->right==NULL) 

    return val; 

  

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

    return treePathsSumUtil(root->left, val) + 

        treePathsSumUtil(root->right, val); 

  
// Функция-обёртка над treePathsSumUtil ()

int treePathsSum(node *root) 

    // Передаем начальное значение как 0

    // так как нет ничего выше root

    return treePathsSumUtil(root, 0); 

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

int main() 

    node *root = newNode(6); 

    root->left = newNode(3); 

    root->right = newNode(5); 

    root->left->left = newNode(2); 

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

    root->right->right = newNode(4); 

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

    root->left->right->right = newNode(4); 

    cout<<"Sum of all paths is "<<treePathsSum(root); 

    return 0; 

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

С

// C программа для поиска суммы всех путей от корня до листьев
#include <stdio.h>
#include <stdlib.h>

  

struct node

{

    int data;

    struct node *left, *right;

};

  
// функция для выделения нового узла с данными

struct node* newNode(int data)

{

    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->data = data;

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

    return (node);

}

  
// Возвращает сумму всех путей от корня к листу. Первый параметр - root
// текущего поддерева, вторым параметром является значение сформированного числа
// по узлам от корня до этого узла

int treePathsSumUtil(struct node *root, int val)

{

    // Базовый вариант

    if (root == NULL)  return 0;

  

    // Обновляем val

    val = (val*10 + root->data);

  

    // если текущим узлом является лист, вернуть текущее значение val

    if (root->left==NULL && root->right==NULL)

       return val;

  

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

    return treePathsSumUtil(root->left, val) +

           treePathsSumUtil(root->right, val);

}

  
// Функция-обёртка над treePathsSumUtil ()

int treePathsSum(struct node *root)

{

    // Передаем начальное значение как 0, так как нет ничего выше root

    return treePathsSumUtil(root, 0);

}

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

int main()

{

    struct node *root = newNode(6);

    root->left        = newNode(3);

    root->right       = newNode(5);

    root->left->left  = newNode(2);

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

    root->right->right = newNode(4);

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

    root->left->right->right = newNode(4);

    printf("Sum of all paths is %d", treePathsSum(root));

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

       

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Возвращает сумму всех путей от корня к листу. Первый параметр

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

    // число, образованное узлами от корня до этого узла

    int treePathsSumUtil(Node node, int val) 

    {

        // Базовый вариант

        if (node == null)

            return 0;

   

        // Обновляем val

        val = (val * 10 + node.data);

   

        // если текущим узлом является лист, вернуть текущее значение val

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

            return val;

   

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

        return treePathsSumUtil(node.left, val)

                + treePathsSumUtil(node.right, val);

    }

   

    // Функция-обёртка над treePathsSumUtil ()

    int treePathsSum(Node node) 

    {

        // Передаем начальное значение как 0, так как нет ничего выше root

        return treePathsSumUtil(node, 0);

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(6);

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

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

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

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

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

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

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

           

        System.out.print("Sum of all paths is "

                                 tree.treePathsSum(tree.root));   

    }    

}

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

питон

# Python программа для поиска суммы всех путей от корня до листьев

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Возвращает суммы всех корневых путей. Первый параметр - root
# текущего поддерева, второй параметр "r это значение числа
# сформированы узлами от корня до этого узла

def treePathsSumUtil(root, val):

  

    # Базовый вариант

    if root is None:

        return 0

  

    # Обновить val

    val = (val*10 + root.data)

  

    # Если текущим узлом является лист, вернуть текущее значение val

    if root.left is None and root.right is None:

        return val

  

    # Повторяющаяся сумма значений для левого и правого поддерева

    return (treePathsSumUtil(root.left, val) + 

            treePathsSumUtil(root.right, val))

  
# Функция-обёртка над treePathSumUtil ()

def treePathsSum(root):

      

    # Передайте начальное значение как 0, так как нет ничего выше root

    return treePathsSumUtil(root, 0)

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

root = Node(6)

root.left = Node(3)

root.right = Node(5)

root.left.left = Node(2)

root.left.right = Node(5)

root.right.right = Node(4)

root.left.right.left = Node(7)

root.left.right.right = Node(4)

print "Sum of all paths is", treePathsSum(root)

  
# Этот код предоставлен 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;

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

public virtual int treePathsSumUtil(Node node,

                                    int val)

{

    // Базовый вариант

    if (node == null)

    {

        return 0;

    }

  

    // Обновляем val

    val = (val * 10 + node.data);

  

    // если текущий узел - лист, возвращаем

    // текущее значение val

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

    {

        return val;

    }

  

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

    return treePathsSumUtil(node.left, val) +

           treePathsSumUtil(node.right, val);

}

  
// Функция-обёртка над treePathsSumUtil ()

public virtual int treePathsSum(Node node)

{

    // Передаем начальное значение как 0

    // нет ничего выше root

    return treePathsSumUtil(node, 0);

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    tree.root = new Node(6);

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

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

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

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

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

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

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

  

    Console.Write("Sum of all paths is "

                   tree.treePathsSum(tree.root));

}
}

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


Выход:

Sum of all paths is 13997

Сложность времени: приведенный выше код представляет собой простой код обхода предзаказа, который происходит каждый раз ровно. Следовательно, временная сложность составляет O (n), где n — количество узлов в данном двоичном дереве.

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

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

Сумма всех чисел, которые сформированы от корневых до листовых путей

0.00 (0%) 0 votes