बाइनरी रूख दिइएमा, तपाईं कसरी आधा नोडहरू हटाउनुहुन्छ?


कठिनाई तह मध्यम
बारम्बार सोधिन्छ समग्र अमेजन माइक्रोसफ्ट PayU स्नैपडल Synopsys याहू
ट्री

समस्या "बाइनरी रूख दिइएमा, कसरी तपाईं सबै आधा नोडहरू हटाउनुहुन्छ?" बताउँछ कि तपाईंलाई बाइनरी रूख दिइन्छ। अब तपाईंले आधा नोडहरू हटाउनु पर्छ। आधा नोड रूखमा नोडको रूपमा परिभाषित हुन्छ जसमा एकल बच्चा हुन्छ। या त यो छोडियो बच्चा वा दायाँ बच्चा।

उदाहरणका

बाइनरी रूख दिइएमा, तपाईं कसरी आधा नोडहरू हटाउनुहुन्छ?

Inorder Traversal of tree after half nodes removal: 5 3 6 2 7

स्पष्टीकरण

मान 4 को साथ नोडको एकल बायाँ बच्चा छ। यसैले यो बाइनरी रूखबाट हटाइएको छ र यसको बायाँ बच्चा रूखमा सारियो। किनभने त्यहाँ केवल एक-आधा नोड छ। यसको हटाए पछि, हामी एक रूखको साथ बाँकी छौं जसको ईन्डर ट्रभर्सल आउटपुटको रूपमा मुद्रित गरियो।

दृष्टिकोण

समस्या एक दिइएको छ बाइनरी रूख, कसरी तपाईं सबै आधा नोडहरू हटाउने? समाधानमा दायाँ जानु भन्दा पहिले। आधा नोड भनेको के हो हामीले थाहा पाउनु पर्छ? आधा नोड बाइनरी रूखमा नोड हो जुन एकल बच्चा हो। न त बच्चा वा दुई बच्चाहरूको एक नोडलाई आधा नोड मानिदैन। अब देखि हामी आधा नोड के हो थाहा छ। हामी समस्याको समाधानको साथ अगाडि बढ्नु पर्छ। समाधान सरल छ। हामी केवल रूखलाई पार गर्दछौं र जब हामी आधा नोड पाउँछौं हामी यसको बच्चासँग बदल्दछौं। हामी जाँच गर्दछौं कि बायाँ बच्चा अवस्थित छ र सहि बच्चा शून्य छ। त्यसपछि हामी यसको बायाँ बच्चा संग अभिभावक (वा आधा नोड) बदल्छौं। त्यस्तै, यदि सही बच्चा मात्र बच्चा हो। सहि बच्चाले अभिभावक नोड प्रतिस्थापन गर्दछ।

कोड

सबै आधा नोडहरू हटाउन C ++ कोड

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* removeHalfNode(node* &root){
    if(!root)
        return NULL;
    if(root->left == NULL && root->right != NULL)
        root = removeHalfNode(root->right);
    else if(root->left != NULL && root->right == NULL)
        root = removeHalfNode(root->left);
    else {
        removeHalfNode(root->left);
        removeHalfNode(root->right);
    }
    return root;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);

  cout<<"Inorder traversal before removing the half nodes"<<endl;
  inorder(root);
  cout<<endl<<"Inorder traversal after removing the half nodes"<<endl;
  root = removeHalfNode(root);
  inorder(root);
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3
Inorder traversal after removing the half nodes
9 7 1 5 3

सबै आधा नोडहरू हटाउन जाभा कोड

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node removeHalfNode(node root){
      if(root == null)
          return null;
      root.left = removeHalfNode(root.left); 
        root.right = removeHalfNode(root.right); 
   
        if(root.left == null && root.right == null) 
            return root;
        if(root.left == null){ 
            node Node = root.right;
            return Node;
        }
        if(root.right == null){ 
            node Node = root.left;
            return Node;
        } 
        return root;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);

    System.out.println("Inorder traversal before removing the half nodes");
    inorder(root);
    System.out.println("\nInorder traversal after removing the half nodes");
    root = removeHalfNode(root);
    inorder(root);
  }
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3 
Inorder traversal after removing the half nodes
9 7 1 5 3

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामीले बाइनरी रूखमा सबै नोडहरू पार गरेका छौं। समय जटिलता रैखिक छ।

ठाउँ जटिलता

ओह), एल्गोरिथ्म एक रिकर्सिव एल्गोरिथ्म हो। यसैले ठाउँ जटिलता कम्पाइलर स्ट्याकमा निर्भर हुन्छ जुन बारीमा रूखको उचाईमा निर्भर हुन्छ।