Compruebe si cada Node del árbol binario tiene un valor K en sí mismo o en sus vecinos inmediatos

Dado un árbol binario y un valor K , la tarea es verificar si cada Node del árbol binario tiene el valor del Node como K o al menos uno de sus Nodes conectados adyacentes tiene el valor K.
 

Ejemplos:  

Input:
                     1
                   /   \
                  0     0
                /   \     \
               1     0     1
              /     /  \    \
             2     1    0    5
                  /    /
                 3    0
                     /
                    0
K = 0
Output: False
Explanation: 
We can observe that some leaf nodes
are having value other than 0 and
are not connected with any
adjacent node whose value is 0. 

Input:
                    0
                   / \
                  2   1
                       \
                        0
K = 0  
Output: True
Explanation: 
Since, all nodes of the tree
are either having value 0 or
connected with adjacent node
having value 0.

Acercarse: 

  1. La idea es simplemente realizar un recorrido de orden previo y pasar la referencia del Node principal de forma recursiva.
  2. Mientras se desplaza por cada Node, verifique las siguientes condiciones: 
    • si el valor del Node es K o,
    • si su valor de Node padre es K o,
    • si alguno de sus valores de Node hijo es K.
  3. Si algún Node del árbol no satisface ninguna de las tres condiciones dadas, devuelve Falso, de lo contrario devuelve Verdadero.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for the above approach
 
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Defining tree node
struct node {
    int value;
    struct node *right, *left;
};
 
// Utility function to create
// a new node
struct node* newnode(int key)
{
    struct node* temp = new node;
    temp->value = key;
    temp->right = NULL;
    temp->left = NULL;
 
    return temp;
}
 
// Function to check binary
// tree whether its every node
// has value K or, it is
// connected with node having
// value K
bool connectedK(node* root,
                node* parent,
                int K,
                bool flag)
{
    // checking node value
    if (root->value != K) {
 
        // checking the left
        // child value
        if (root->left == NULL
            || root->left->value != K) {
 
            // checking the right
            // child value
            if (root->right == NULL
                || root->right->value != K) {
 
                // checking the parent value
                if (parent == NULL
                    || parent->value != K) {
                    flag = false;
                    return flag;
                }
            }
        }
    }
 
    // Traversing to the left subtree
    if (root->left != NULL) {
        if (flag == true) {
            flag
                = connectedK(root->left,
                            root, K, flag);
        }
    }
 
    // Traversing to the right subtree
    if (root->right != NULL) {
        if (flag == true) {
            flag
                = connectedK(root->right,
                            root, K, flag);
        }
    }
    return flag;
}
 
// Driver code
int main()
{
 
    // Input Binary tree
    struct node* root = newnode(0);
    root->right = newnode(1);
    root->right->right = newnode(0);
    root->left = newnode(0);
 
    int K = 0;
 
    // Function call to check
    // binary tree
    bool result
        = connectedK(root, NULL,
                    K, true);
 
    if (result == false)
        cout << "False\n";
    else
        cout << "True\n";
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Defining tree node
static class node
{
    int value;
    node right, left;
};
 
// Utility function to create
// a new node
static node newnode(int key)
{
    node temp = new node();
    temp.value = key;
    temp.right = null;
    temp.left = null;
 
    return temp;
}
 
// Function to check binary
// tree whether its every node
// has value K or, it is
// connected with node having
// value K
static boolean connectedK(node root,
                          node parent,
                          int K,
                          boolean flag)
{
    // Checking node value
    if (root.value != K)
    {
 
        // Checking the left
        // child value
        if (root.left == null ||
            root.left.value != K)
        {
 
            // Checking the right
            // child value
            if (root.right == null ||
                root.right.value != K)
            {
 
                // Checking the parent value
                if (parent == null ||
                    parent.value != K)
                {
                    flag = false;
                    return flag;
                }
            }
        }
    }
 
    // Traversing to the left subtree
    if (root.left != null)
    {
        if (flag == true)
        {
            flag = connectedK(root.left,
                              root, K, flag);
        }
    }
 
    // Traversing to the right subtree
    if (root.right != null)
    {
        if (flag == true)
        {
            flag = connectedK(root.right,
                              root, K, flag);
        }
    }
    return flag;
}
 
// Driver code
public static void main(String[] args)
{
 
    // Input Binary tree
    node root = newnode(0);
    root.right = newnode(1);
    root.right.right = newnode(0);
    root.left = newnode(0);
 
    int K = 0;
 
    // Function call to check
    // binary tree
    boolean result = connectedK(root, null,
                                   K, true);
 
    if (result == false)
        System.out.print("False\n");
    else
        System.out.print("True\n");
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program for the above approach
 
# Defining tree node
class Node:
    def __init__(self,key):
         
        self.value = key
        self.left = None
        self.right = None
         
# Function to check binary
# tree whether its every node
# has value K or, it is
# connected with node having
# value K
def connectedK(root, parent, K, flag):
     
    # Checking node value
    if root.value != K:
         
        # Checking the left
        # child value
        if (root.left == None or
            root.left.value != K):
             
            # Checking the right
            # child value
            if (root.right == None or
                root.right.value != K):
                 
                # Checking the parent value
                if (parent == None or
                    parent.value != K):
                    flag = False
                    return flag
                 
    # Traversing to the left subtree
    if root.left != None:
        if flag == True:
            flag = connectedK(root.left,
                              root, K, flag)
     
    # Traversing to the right subtree
    if root.right != None:
        if flag == True:
            flag = connectedK(root.right,
                              root, K, flag)
             
    return flag
 
# Driver code
root = Node(0)
root.right = Node(1)
root.right.right = Node(0)
root.left = Node(0)
 
K = 0
 
# Function call to check
# binary tree
result = connectedK(root, None, K, True)
 
if result == False:
    print("False")
else:
    print("True")
 
# This code is contributed by Stuti Pathak

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Defining tree node
class node
{
    public int value;
    public node right, left;
};
 
// Utility function to create
// a new node
static node newnode(int key)
{
    node temp = new node();
    temp.value = key;
    temp.right = null;
    temp.left = null;
 
    return temp;
}
 
// Function to check binary
// tree whether its every node
// has value K or, it is
// connected with node having
// value K
static bool connectedK(node root,
                       node parent,
                       int K,
                       bool flag)
{
     
    // Checking node value
    if (root.value != K)
    {
 
        // checking the left
        // child value
        if (root.left == null ||
            root.left.value != K)
        {
 
            // Checking the right
            // child value
            if (root.right == null ||
                root.right.value != K)
            {
 
                // Checking the parent value
                if (parent == null ||
                    parent.value != K)
                {
                    flag = false;
                    return flag;
                }
            }
        }
    }
 
    // Traversing to the left subtree
    if (root.left != null)
    {
        if (flag == true)
        {
            flag = connectedK(root.left,
                              root, K, flag);
        }
    }
 
    // Traversing to the right subtree
    if (root.right != null)
    {
        if (flag == true)
        {
            flag = connectedK(root.right,
                              root, K, flag);
        }
    }
    return flag;
}
 
// Driver code
public static void Main(String[] args)
{
 
    // Input Binary tree
    node root = newnode(0);
    root.right = newnode(1);
    root.right.right = newnode(0);
    root.left = newnode(0);
 
    int K = 0;
 
    // Function call to check
    // binary tree
    bool result = connectedK(root, null,
                                K, true);
 
    if (result == false)
        Console.Write("False\n");
    else
        Console.Write("True\n");
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
    // Javascript program for the above approach
     
    // Defining tree node
    class node
    {
        constructor(key) {
           this.value = key;
           this.left = this.right = null;
        }
    }
 
    // Utility function to create
    // a new node
    function newnode(key)
    {
        let temp = new node(key);
        return temp;
    }
 
    // Function to check binary
    // tree whether its every node
    // has value K or, it is
    // connected with node having
    // value K
    function connectedK(root, parent, K, flag)
    {
        // Checking node value
        if (root.value != K)
        {
 
            // Checking the left
            // child value
            if (root.left == null ||
                root.left.value != K)
            {
 
                // Checking the right
                // child value
                if (root.right == null ||
                    root.right.value != K)
                {
 
                    // Checking the parent value
                    if (parent == null ||
                        parent.value != K)
                    {
                        flag = false;
                        return flag;
                    }
                }
            }
        }
 
        // Traversing to the left subtree
        if (root.left != null)
        {
            if (flag == true)
            {
                flag = connectedK(root.left, root, K, flag);
            }
        }
 
        // Traversing to the right subtree
        if (root.right != null)
        {
            if (flag == true)
            {
                flag = connectedK(root.right, root, K, flag);
            }
        }
        return flag;
    }
     
    // Input Binary tree
    let root = newnode(0);
    root.right = newnode(1);
    root.right.right = newnode(0);
    root.left = newnode(0);
   
    let K = 0;
   
    // Function call to check
    // binary tree
    let result = connectedK(root, null, K, true);
   
    if (result == false)
        document.write("False");
    else
        document.write("True");
 
</script>

Producción:  

True

Complejidad temporal: O(N), N es el número de Nodes del árbol. 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *