Рубрики

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

Деревья

Дано Бинарное Дерево с различными узлами. Учитывая два узла node1 и node2 , проверьте, лежат ли два узла в одном поддереве корневого узла. То есть любое из левого и правого поддеревьев корневого узла.

Например : в приведенном выше двоичном дереве узлы 3 и 8 находятся в одном и том же поддереве, а 4 и 5 — в другом поддереве.

Предварительное условие : проверьте, существует ли узел в двоичном дереве .

Идея похожа на поиск узла в двоичном дереве. Есть четыре разных случая:

  1. Если оба узла node1 и node2 находятся в левом поддереве корневого узла.
  2. Если оба узла 1 и 2 находятся в правом поддереве корневого узла.
  3. Если узел 1 находится в левом поддереве корневого узла, а узел 2 — в правом поддереве корневого узла.
  4. Если узел 1 находится в правом поддереве корневого узла, а узел 2 находится в левом поддереве корневого узла.

Используйте подход поиска узла в двоичном дереве и проверьте, является ли какой-либо из первых двух случаев, перечисленных выше, истинным. Если любой из первых двух случаев, перечисленных выше, найден True, выведите YES, иначе выведите NO.

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

C ++

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

  
#include <iostream>

using namespace std;

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

struct Node {

    int data;

    struct Node *left, *right;

    Node(int data)

    {

        this->data = data;

        left = right = NULL;

    }

};

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

bool ifNodeExists(struct Node* node, int key)

{

    if (node == NULL)

        return false;

  

    if (node->data == key)

        return true;

  

    / * затем возвращаемся на левое дерево * /

    bool res1 = ifNodeExists(node->left, key);

  

    / * теперь возвращаемся на правильное поддерево * /

    bool res2 = ifNodeExists(node->right, key);

  

    return res1 || res2;

}

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

bool ifSameSubTree(Node* root, int node1, int node2)

{

    if (root == NULL)

       return false;

  

    // Случай 1: Если оба узла находятся в левом поддереве

    if (ifNodeExists(root->left, node1)

        && ifNodeExists(root->left, node2)) {

        return true;

    }

  

    // Случай 2: если оба узла находятся в правом поддереве

    else if (ifNodeExists(root->right, node1)

             && ifNodeExists(root->right, node2)) {

        return true;

    }

  

    // Случай 3 и 4: узлы находятся в разных поддеревьях

    else

        return false;

}

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

int main()

{

    struct Node* root = new Node(0);

    root->left = new Node(1);

    root->left->left = new Node(3);

    root->left->left->left = new Node(7);

    root->left->right = new Node(4);

    root->left->right->left = new Node(8);

    root->left->right->right = new Node(9);

    root->right = new Node(2);

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

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

  

    int node1 = 3, node2 = 8;

  

    if (ifSameSubTree(root, node1, node2))

        cout << "YES";

    else

        cout << "NO";

  

    return 0;

}

Джава

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

import java.util.*;

class solution

{

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

 static class Node { 

    int data; 

     Node left, right; 

    Node(int data) 

    { 

        this.data = data; 

        left = right = null; 

    } 

} 

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

static boolean ifNodeExists( Node node, int key) 

{ 

    if (node == null) 

        return false; 

  

    if (node.data == key) 

        return true; 

  

    / * затем возвращаемся на левое дерево * /

    boolean res1 = ifNodeExists(node.left, key); 

  

    / * теперь возвращаемся на правильное поддерево * /

    boolean res2 = ifNodeExists(node.right, key); 

  

    return res1 || res2; 

} 

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

static boolean ifSameSubTree(Node root, int node1, int node2) 

{ 

    if (root == null) 

    return false; 

  

    // Случай 1: Если оба узла находятся в левом поддереве

    if (ifNodeExists(root.left, node1) 

        && ifNodeExists(root.left, node2)) { 

        return true; 

    } 

  

    // Случай 2: если оба узла находятся в правом поддереве

    else if (ifNodeExists(root.right, node1) 

            && ifNodeExists(root.right, node2)) { 

        return true; 

    } 

  

    // Случай 3 и 4: узлы находятся в разных поддеревьях

    else

        return false; 

} 

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

public static void main(String args[])

{ 

     Node root = new Node(0); 

    root.left = new Node(1); 

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

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

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

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

    root.left.right.right = new Node(9); 

    root.right = new Node(2); 

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

    root.right.right = new Node(6); 

  

    int node1 = 3, node2 = 8; 

  

    if (ifSameSubTree(root, node1, node2)) 

        System.out.println("YES"); 

    else

        System.out.println( "NO"); 

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

python3

"" "Программа Python3 для проверки наличия двух узлов
находятся в тех же поддеревьях корневого узла "" "

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

class newNode: 

  

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

    def __init__(self, data): 

        self.data= data 

        self.left = None

        self.right = None

        self.visited = False

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

def ifNodeExists(node, key) :

    if (node == None):

        return False

  

    if (node.data == key):

        return True

  

    "" "затем возвращаемся на левое дерево" ""

    res1 = ifNodeExists(node.left, key) 

  

    "" "теперь возвращаемся на правильное поддерево" ""

    res2 = ifNodeExists(node.right, key) 

  

    return res1 or res2 

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

def ifSameSubTree(root, node1, node2):

  

    if (root == None) :

        return False

  

    # ПРИМЕР 1: Если оба узла находятся в

    # левое поддерево

    if (ifNodeExists(root.left, node1) 

        and ifNodeExists(root.left, node2)):

        return True

  

    # ПРИМЕР 2: Если оба узла находятся в

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

    elif (ifNodeExists(root.right, node1) 

            and ifNodeExists(root.right, node2)):

        return True

      

    # ПРИМЕРЫ 3 и 4: Узлы находятся в

    # разные поддеревья

    else:

        return False

                          
Код водителя

if __name__ == '__main__':

    root = newNode(0) 

    root.left = newNode(1) 

    root.left.left = newNode(3) 

    root.left.left.left = newNode(7) 

    root.left.right = newNode(4) 

    root.left.right.left = newNode(8) 

    root.left.right.right = newNode(9) 

    root.right = newNode(2) 

    root.right.left = newNode(5) 

    root.right.right = newNode(6) 

  

    node1 = 3

    node2 = 8

  

    if (ifSameSubTree(root, node1, node2)):

        print("YES") 

    else:

        print("NO")

  
# Этот код предоставлен
# SHUBHAMSINGH10

C #

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

using System;

  

class GFG

{ 

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

class Node

{ 

    public int data; 

    public Node left, right; 

    public Node(int data) 

    { 

        this.data = data; 

        left = right = null; 

    } 

} 

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

static bool ifNodeExists( Node node, int key) 

{ 

    if (node == null) 

        return false; 

  

    if (node.data == key) 

        return true; 

  

    / * затем возвращаемся на левое дерево * /

    bool res1 = ifNodeExists(node.left, key); 

  

    / * теперь возвращаемся на правильное поддерево * /

    bool res2 = ifNodeExists(node.right, key); 

  

    return res1 || res2; 

} 

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

static bool ifSameSubTree(Node root,

                int node1, int node2) 

{ 

    if (root == null) 

    return false; 

  

    // Случай 1: Если оба узла находятся в левом поддереве

    if (ifNodeExists(root.left, node1) 

        && ifNodeExists(root.left, node2)) 

    { 

        return true; 

    } 

  

    // Случай 2: если оба узла находятся в правом поддереве

    else if (ifNodeExists(root.right, node1) 

            && ifNodeExists(root.right, node2)) 

    { 

        return true; 

    } 

  

    // Случай 3 и 4: узлы находятся в разных поддеревьях

    else

        return false; 

} 

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

public static void Main() 

{ 

    Node root = new Node(0); 

    root.left = new Node(1); 

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

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

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

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

    root.left.right.right = new Node(9); 

    root.right = new Node(2); 

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

    root.right.right = new Node(6); 

  

    int node1 = 3, node2 = 8; 

  

    if (ifSameSubTree(root, node1, node2)) 

        Console.WriteLine("YES"); 

    else

        Console.WriteLine( "NO"); 

  
} 
} 

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

Выход:

YES

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

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

0.00 (0%) 0 votes