Рубрики

Сумма всех нечетных узлов в пути, соединяющих два заданных узла

Дано двоичное дерево и два узла этого двоичного дерева. Найти сумму всех узлов с нечетными значениями в пути, соединяющем два заданных узла.

Например : в приведенном выше двоичном дереве сумма всех нечетных узлов на пути между узлами и будет 5 + 1 + 3 = 9 .

Источник : Amazon Интервью Опыт в кампусе

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

После того, как у нас есть путь между двумя заданными узлами, вычисляем сумму всех нечетных узлов в этом пути и печатаем его.

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

C ++

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

  
#include<bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

};

  
// Utitlity функция для создания
// новый узел двоичного дерева

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

      

    return node;

}

  
// Функция для проверки наличия пути от root
// к данному узлу. Это также населяет
// 'arr' с заданным путем

bool getPath(Node* root, vector<int>& arr, int x) 

    // если root равен NULL

    // пути нет

    if (!root) 

        return false

  

    // помещаем значение узла в 'arr'

    arr.push_back(root->data); 

  

    // если это обязательный узел

    // вернуть true

    if (root->data == x) 

        return true

  

    // еще проверить, лежит ли нужный узел

    // в левом поддереве или правом поддереве

    // текущий узел

    if (getPath(root->left, arr, x) || getPath(root->right, arr, x)) 

        return true

  

    // обязательный узел не лежит ни в

    // левое или правое поддерево текущего узла

    // Таким образом, удаляем значение текущего узла из

    // 'arr'и возвращаем false

    arr.pop_back(); 

    return false

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

int sumOddNodes(Node* root, int n1, int n2) 

    // вектор для хранения пути

    // первый узел n1 от корня

    vector<int> path1; 

  

    // вектор для хранения пути

    // второй узел n2 от корня

    vector<int> path2; 

  

    getPath(root, path1, n1); 

    getPath(root, path2, n2); 

  

    int intersection = -1; 

  

    // Получить точку пересечения

    int i = 0, j = 0; 

    while (i != path1.size() || j != path2.size()) { 

  

        // Продолжайте двигаться вперед до пересечения

        // находится

        if (i == j && path1[i] == path2[j]) { 

            i++; 

            j++; 

        

        else

            intersection = j - 1; 

            break

        

    

      

    int sum = 0;

      

    // вычисляем сумму узлов ODD по пути

    for (int i = path1.size() - 1; i > intersection; i--) 

        if(path1[i]%2)

            sum += path1[i];

  

    for (int i = intersection; i < path2.size(); i++) 

        if(path2[i]%2)

            sum += path2[i];

              

    return sum;        

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

int main()

{

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

      

    int node1 = 5; 

    int node2 = 6; 

      

    cout<<sumOddNodes(root, node1, node2); 

      

    return 0;

Джава

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

  

import java.util.*;

class solution

{

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

static class Node 

    int data; 

     Node left; 

     Node right; 

  
// Utitlity функция для создания
// новый узел двоичного дерева

 static Node newNode(int data) 

     Node node = new Node(); 

    node.data = data; 

    node.left = null

    node.right = null

      

    return node; 

  
// Функция для проверки наличия пути от root
// к данному узлу. Это также населяет
// 'arr' с заданным путем

static boolean getPath(Node root, Vector<Integer> arr, int x) 

    // если root имеет значение null

    // пути нет

    if (root==null

        return false

  

    // помещаем значение узла в 'arr'

    arr.add(root.data); 

  

    // если это обязательный узел

    // вернуть true

    if (root.data == x) 

        return true

  

    // еще проверить, лежит ли нужный узел

    // в левом поддереве или правом поддереве

    // текущий узел

    if (getPath(root.left, arr, x) || getPath(root.right, arr, x)) 

        return true

  

    // обязательный узел не лежит ни в

    // левое или правое поддерево текущего узла

    // Таким образом, удаляем значение текущего узла из

    // 'arr'и возвращаем false

    arr.remove(arr.size()-1); 

    return false

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

static int sumOddNodes(Node root, int n1, int n2) 

    // вектор для хранения пути

    // первый узел n1 от корня

    Vector<Integer> path1= new Vector<Integer>(); 

  

    // вектор для хранения пути

    // второй узел n2 от корня

    Vector<Integer> path2= new Vector<Integer>(); 

  

    getPath(root, path1, n1); 

    getPath(root, path2, n2); 

  

    int intersection = -1

  

    // Получить точку пересечения

    int i = 0, j = 0

    while (i != path1.size() || j != path2.size()) { 

  

        // Продолжайте двигаться вперед до пересечения

        // находится

        if (i == j && path1.get(i) == path2.get(j)) { 

            i++; 

            j++; 

        

        else

            intersection = j - 1

            break

        

    

      

    int sum = 0

      

    // вычисляем сумму узлов ODD по пути

    for (i = path1.size() - 1; i > intersection; i--) 

        if(path1.get(i)%2!=0

            sum += path1.get(i); 

  

    for (i = intersection; i < path2.size(); i++) 

        if(path2.get(i)%2!=0

            sum += path2.get(i); 

              

    return sum;         

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

public static void main(String args[]) 

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

      

    int node1 = 5

    int node2 = 6

      

    System.out.print(sumOddNodes(root, node1, node2)); 

      

}


Выход:

9

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

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

Сумма всех нечетных узлов в пути, соединяющих два заданных узла

0.00 (0%) 0 votes