Рубрики

Измените двоичное дерево так, чтобы каждый узел сохранял сумму всех узлов в левом поддереве

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

Примеры:

Input : 
     1
   /   \
 2      3

Output :
    3
  /   \
 2     3


Input
       1
      / \
     2   3
    / \   \
   4   5   6
Output:
      12
     / \
    6   3
   / \   \
  4   5   6

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

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

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std; 

  
// Узел дерева

class node 

    public:

    int data; 

    node* left, *right; 

      

    / * Конструктор, который выделяет новый узел с

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

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

}; 

  
// Функция для изменения двоичного дерева
// так что каждый узел хранит сумму
// значения в его левом потомке, включая
// свое значение

int updatetree(node *root) 

    // Базовые случаи

    if (!root) 

        return 0; 

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

        return root->data; 

  

    // Обновляем левое и правое поддеревья

    int leftsum = updatetree(root->left); 

    int rightsum = updatetree(root->right); 

  

    // Добавить левую сумму в текущий узел

    root->data += leftsum; 

  

    // Возвращаем сумму значений под корнем

    return root->data + rightsum; 

  
// Сервисная функция для выполнения обхода inorder

void inorder(node* node) 

    if (node == NULL) 

        return

    inorder(node->left); 

    cout<<node->data<<" "

    inorder(node->right); 

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

int main() 

    / * Давайте построим ниже дерева

                1

            / /

            2 3

            ///

            4 5 6 * /

    struct node *root = new node(1); 

    root->left     = new node(2); 

    root->right = new node(3); 

    root->left->left = new node(4); 

    root->left->right = new node(5); 

    root->right->right = new node(6); 

  

    updatetree(root); 

  

    cout << "Inorder traversal of the modified tree is: \n"

    inorder(root); 

    return 0; 

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

С

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

using namespace std;

  
// Узел дерева

struct node

{

    int data;

    struct node* left,  *right;

};

  
// Функция для изменения бинарного дерева, чтобы каждый узел
// сохраняет сумму значений в левом дочернем элементе, включая его
// собственная стоимость

int updatetree(node *root)

{

    // Базовые случаи

    if (!root)

        return 0;

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

        return root->data;

  

    // Обновляем левое и правое поддеревья

    int leftsum  = updatetree(root->left);

    int rightsum = updatetree(root->right);

  

    // Добавить левую сумму в текущий узел

    root->data += leftsum;

  

    // Возвращаем сумму значений под корнем

    return root->data + rightsum;

}

  
// Сервисная функция для выполнения обхода inorder

void inorder(struct node* node)

{

    if (node == NULL)

        return;

    inorder(node->left);

    printf("%d ", node->data);

    inorder(node->right);

}

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

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()

{

    / * Давайте построим ниже дерева

                1

               / /

              2 3

             ///

            4 5 6 * /

    struct node *root  = newNode(1);

    root->left         = newNode(2);

    root->right        = newNode(3);

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

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

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

  

    updatetree(root);

  

    cout << "Inorder traversal of the modified tree is \n";

    inorder(root);

    return 0;

}

Джава

// Java-программа для хранения суммы узлов в левом поддереве в каждом
// узел

class GfG { 

  
// Узел дерева

static class node 

    int data; 

    node left, right; 

}

  
// Функция для изменения бинарного дерева, чтобы каждый узел
// сохраняет сумму значений в левом дочернем элементе, включая его
// собственная стоимость

static int updatetree(node root) 

    // Базовые случаи

    if (root == null

        return 0

    if (root.left == null && root.right == null

        return root.data; 

  

    // Обновляем левое и правое поддеревья

    int leftsum = updatetree(root.left); 

    int rightsum = updatetree(root.right); 

  

    // Добавить левую сумму в текущий узел

    root.data += leftsum; 

  

    // Возвращаем сумму значений под корнем

    return root.data + rightsum; 

  
// Сервисная функция для выполнения обхода inorder

static void inorder(node node) 

    if (node == null

        return

    inorder(node.left); 

    System.out.print(node.data + " "); 

    inorder(node.right); 

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

static node newNode(int data) 

    node node = new node(); 

    node.data = data; 

    node.left = null

    node.right = null

    return(node); 

  
// Драйвер программы

public static void main(String[] args) 

    / * Давайте построим ниже дерева

                1

            / /

            2 3

            ///

            4 5 6 * /

    node root = newNode(1); 

    root.left         = newNode(2); 

    root.right     = newNode(3); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

    root.right.right = newNode(6); 

  

    updatetree(root); 

  

      

    System.out.println("Inorder traversal of the modified tree is"); 

    inorder(root); 


python3

# Python3 программа для хранения суммы узлов
# в левом поддереве в каждом узле

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

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

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# Функция для изменения двоичного дерева так
# что каждый узел хранит сумму значений
# в его левом потомке, включая его собственную ценность

def updatetree(root):

      

    # Базовые случаи

    if (not root): 

        return 0

    if (root.left == None and

        root.right == None) :

        return root.data 

  

    # Обновление левого и правого поддеревьев

    leftsum = updatetree(root.left) 

    rightsum = updatetree(root.right) 

  

    # Добавить левую сумму в текущий узел

    root.data += leftsum 

  

    # Возвращаем сумму значений под корнем

    return root.data + rightsum 

  
# Утилита для выполнения обхода inorder

def inorder(node) :

  

    if (node == None) :

        return

    inorder(node.left) 

    print(node.data, end = " "

    inorder(node.right) 

  
Код водителя

if __name__ == '__main__':

      

    "" "Давайте миновать дерево ниже

                    1

                / /

                2 3

                ///

                4 5 6 "" "

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

    root.right.right = newNode(6

  

    updatetree(root) 

  

    print("Inorder traversal of the modified tree is"

    inorder(root)

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

C #

// C # программа для хранения суммы узлов слева
// поддерево в каждом узле

using System;

  

class GfG 

  
// Узел дерева

class node 

    public int data; 

    public node left, right; 

  
// Функция для изменения двоичного дерева так
// каждый узел хранит сумму значений
// в его левом потомке, включая его собственное значение

static int updatetree(node root) 

    // Базовые случаи

    if (root == null

        return 0; 

    if (root.left == null && root.right == null

        return root.data; 

  

    // Обновляем левое и правое поддеревья

    int leftsum = updatetree(root.left); 

    int rightsum = updatetree(root.right); 

  

    // Добавить левую сумму в текущий узел

    root.data += leftsum; 

  

    // Возвращаем сумму значений под корнем

    return root.data + rightsum; 

  
// Сервисная функция для выполнения обхода inorder

static void inorder(node node) 

    if (node == null

        return

    inorder(node.left); 

    Console.Write(node.data + " "); 

    inorder(node.right); 

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

static node newNode(int data) 

    node node = new node(); 

    node.data = data; 

    node.left = null

    node.right = null

    return(node); 

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

public static void Main() 

    / * Давайте построим ниже дерева

                1

            / /

            2 3

            ///

            4 5 6 * /

    node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

    root.right.right = newNode(6); 

  

    updatetree(root); 

  

    Console.WriteLine("Inorder traversal of the modified tree is"); 

    inorder(root); 


  
/ * Этот код предоставлен Rajput-Ji * /


Выход:

Inorder traversal of the modified tree is
4 6 5 12 3 6

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

Спасибо Гаураву Арирвару за предложение этого решения.

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

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

Измените двоичное дерево так, чтобы каждый узел сохранял сумму всех узлов в левом поддереве

0.00 (0%) 0 votes