Рубрики

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

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

Примеры:

Input : 
     1
   /   \
 2      3
Output : 
    4
  /   \
 2     3

Input : 
       1
      / \
     2   3
    / \   \
   4   5   6
Output :
       10
      / \
     7   9
    / \   \
   4   5   6

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

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

C ++

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

using namespace std;

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

struct Node {

    int data;

    Node *left, *right;

};

  
// Функция для создания нового узла

struct Node* createNode(int item)

{

    Node* temp = new Node;

    temp->data = item;

    temp->left = NULL;

    temp->right = NULL;

  

    return temp;

}

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

int updateBTree(Node* root)

{

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

    if (!root)

        return 0;

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

        return root->data;

  

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

    int rightsum = updateBTree(root->right);

    int leftsum = updateBTree(root->left);

  

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

    root->data += rightsum;

  

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

    return root->data + leftsum;

}

  
// Функция обхода дерева по порядку

void inorder(struct 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 = NULL;

    root = createNode(1);

    root->left = createNode(2);

    root->right = createNode(3);

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

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

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

  

    // строительство нового дерева

    updateBTree(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 Node createNode(int item) 

    Node temp = new Node(); 

    temp.data = item; 

    temp.left = null

    temp.right = null

  

    return temp; 

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

static int updateBTree(Node root) 

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

    if (root == null

        return 0

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

        return root.data; 

  

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

    int rightsum = updateBTree(root.right); 

    int leftsum = updateBTree(root.left); 

  

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

    root.data += rightsum; 

  

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

    return root.data + leftsum; 

  
// Функция обхода дерева по порядку

static void inorder( Node node) 

    if (node == null

        return

    inorder(node.left); 

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

    inorder(node.right); 

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

public static void main(String args[])

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

        1

        / /

        2 3

        ///

        4 5 6 * /

    Node root = null

    root = createNode(1); 

    root.left = createNode(2); 

    root.right = createNode(3); 

    root.left.left = createNode(4); 

    root.left.right = createNode(5); 

    root.right.right = createNode(6); 

  

    // новое дерево

    updateBTree(root); 

  

    System.out.print( "Inorder traversal of the modified tree is \n"); 

    inorder(root); 

}

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

python3

# Программа для преобразования дерева выражений
# из префиксного выражения

  
# Вспомогательная функция, которая выделяет новый
# узел с заданными данными и None
# левый и правый пиры

class createNode: 

  

    # Conto создать новый узел

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

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

def updateBTree( root):

  

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

    if (not root):

        return 0

    if (root.left == None and

        root.right == None):

        return root.data

  

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

    rightsum = updateBTree(root.right)

    leftsum = updateBTree(root.left)

  

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

    root.data += rightsum

  

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

    return root.data + leftsum

  
# Функция обхода дерева по порядку

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 = None

    root = createNode(1)

    root.left = createNode(2)

    root.right = createNode(3)

    root.left.left = createNode(4)

    root.left.right = createNode(5)

    root.right.right = createNode(6)

  

    # строительство нового дерева

    updateBTree(root)

  

    print("Inorder traversal of the"

          "modified tree is")

    inorder(root)

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

C #

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

using System;

      

class GFG

{

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

public class Node 

    public int data; 

    public Node left, right; 

}; 

  
// Функция для создания нового узла

static Node createNode(int item) 

    Node temp = new Node(); 

    temp.data = item; 

    temp.left = null

    temp.right = null

  

    return temp; 

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

static int updateBTree(Node root) 

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

    if (root == null

        return 0; 

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

        return root.data; 

  

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

    int rightsum = updateBTree(root.right); 

    int leftsum = updateBTree(root.left); 

  

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

    root.data += rightsum; 

  

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

    return root.data + leftsum; 

  
// Функция обхода дерева по порядку

static void inorder( Node node) 

    if (node == null

        return

    inorder(node.left); 

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

    inorder(node.right); 

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

public static void Main(String[] args)

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

        1

        / /

        2 3

        ///

        4 5 6 * /

    Node root = null

    root = createNode(1); 

    root.left = createNode(2); 

    root.right = createNode(3); 

    root.left.left = createNode(4); 

    root.left.right = createNode(5); 

    root.right.right = createNode(6); 

  

    // новое дерево

    updateBTree(root); 

  

    Console.Write( "Inorder traversal of the modified tree is \n"); 

    inorder(root); 

}
}

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

Выход:

Inorder traversal of the modified tree is 
4 7 5 10 9 6

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

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

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

0.00 (0%) 0 votes