بائنري وڻ کي ڏنو ، توهان سڀ اڌ ناڊس ڪيئن ڪ removeو ٿا؟


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ قبول ڪريو Amazon Microsoft جي پي يو يو اسپيڊل ڪنڊوزس ياهو
وڻن

مسئلو "هڪ بائنري وڻ کي ڏنو ، توهان ڪئين اڌ اڌڊس کي ڪيئن هٽايو؟" اهو ٻڌائي ٿو ته توهان کي هڪ بائنري وڻ ڏنو ويو آهي. هاڻي توهان کي اڌ نوڊز کي هٽائڻ جي ضرورت آهي. اڌ نوڊ وڻ ۾ نوڊ طور بيان ڪيو ويو آهي جيڪو صرف هڪ ئي ٻار آهي. يا ته اهو ٻار ڇڏي ويو آهي يا سا rightي ٻار.

مثال

بائنري وڻ کي ڏنو ، توهان سڀ اڌ ناڊس ڪيئن ڪ removeو ٿا؟

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

وضاحت

قيمت 4 سان جوڙ جوڙيل هڪڙي کاٻي ٻار کي آهي. اهڙيءَ طرح هن کي بائنري وڻ مان ڪ hasيو ويو آهي ۽ ان جو کاٻي ٻار وڻ کي مٿي وڌائي چڪو آهي. ڇو ته هتي فقط هڪ اڌ نوڊ آهي. ان جي ختم ٿيڻ کان پوءِ ، اسان هڪ وڻ سان گڏ رهجي ويا آهيون جنهن جي انڊرورس ٽرورسل کي پيداوار طور پرنٽ ڪيو ويو آهي.

چرچو

مسئلو هڪ ڏني آهي بائنري وڻ، توهان اڌ ڪئين نوڊس ڪيئن هٽائي ڇڏيو؟ حل ۾ صحيح ٽپو ڏيڻ کان اڳ. اسان کي پهريان knowاڻڻ گهرجي ته هڪ اڌ نوڊ ڇا آهي؟ اڌ نوڊ ثاندي وڻ ۾ هڪ نوڊ آهي جنهن جو هڪڙو ٻار آهي. اھڙيءَ طرح ڪنھن ٻار يا ٻن ٻارن سان گڏ ھڪڙو نن halfڙو حصو نه سمجهيو ويندو آھي. ھاڻي کان اسين weاڻون ٿا ته اڌ نوڊ ڇا آھي. اسان کي اڳتي وڌڻ گهرجي مسئلي جي حل سان. حل سادو آهي. اسان وڻ کي آسانيءَ سان پار ڪريون ٿا ۽ جڏهن ڪڏهن اڌ پاسو ڳوليندا آهيون اسين ان جي ٻار سان بدلائيندا آهيون. اسان پڙتال ڪئي ته کاٻي ٻار موجود آهي ۽ صحيح ٻار نئون آهي. پوءِ اسان والدين کي ڇڏي ڏيو (يا اڌ نوڊ) ان جي کاٻي ٻار سان. اهڙي طرح ، جيڪڏهن صحيح ٻار اڪيلو ٻار آهي. صحيح ٻار والدين نوڊ کي تبديل ڪري ٿو.

ڪوڊ

سي ++ ڪوڊ سڀ اڌ نوڊس کي ڪ toڻ لاءِ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان بائنري وڻ ۾ سڀني نوڊس کان وڌي چڪا آهيون. وقت جي پيچيدگي لڪيل آهي.

خلائي پيچيدگي

اي (ايڇ) ، الگورٿم هڪ تجريدي الگورتھم آهي. اھڙي طرح خلائي پيچيدگي مرتب ڪندڙ اسٽيڪ تي منحصر آھي جنھن جي نتيجي ۾ وڻ جي اوچائي تي منحصر آھي.