بائنري وڻ جي حدن جو ٽرانسورس


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ قبول ڪريو Amazon چڙهڻ تنقيدي حل Microsoft جي مارگن Stanley پي يو يو اسپيڊل
بائنري وڻ وڻن وڻ ٽرانسورس

مسئلي جو بيان

مسئلو ”بائنري ٽرنر جي بائونڊري ٽرانسورس“ ٻڌائي ٿو ته توهان کي بائنري وڻ ڏنو ويو آهي. ھاڻي توھان کي چؤديواري جي حد ڏسڻ جي پرنٽ ڪرڻ جي ضرورت آھي بائنري وڻ. هتي حد جي دائري جو مطلب آهي ته سڀني نوڊس وڻ جي حد طور ظاهر ڪيا ويا آهن. نوڊس مٿين پاسي ، کاٻي طرف ، هيٺيون پاسي ۽ سا rightي طرف کان ڏسندا آهن. پر جيڪڏهن اسان سڌي طور تي اهي سڀ نظارا ڇپائي سگهون ها ته ساڳيا ئي نوڊس جي ڇپائي جو عمل ڪيترائي ڀيرا ٿي ويندو. تنهنڪري حد جي ڏيک کي پرنٽ ڪيو ته جيئن نوڊس ورجائي نه ٿين.

مثال

2 3 5 6 4 7

وضاحت

هتي ، سڀئي نوڊس حد بندي ٿيل نوڊس آهن. پر اسان کي گهرجي ته نوڊس کي مخالف گھڙي وار خلاف هدايت ۾ پيش ڪريون. اهڙي طرح اسان روٽ کان شروع ڪريون ٿا جيڪو 2 آهي. پوءِ ، اسان بس ساڳي طريقي سان اڳتي وڌون ٿا ۽ نوڊس 2 ، 3 ، 4 ، 6 ، 4 ، 7 ڇپايون ٿا.

بائنري وڻ جي حدن جو ٽرانسورس

5 7 9 1 4 3

چرچو

مسئلو اسان کان وڻ جي حد کي ڇپائڻ لاءِ پڇي ٿو ، هتي اسان کي ڇڏي چڪا آهيون ، صحيح ۽ هيٺيون حد. جيڪڏھن وڻ کي ڪنھن به کاٻي يا سا boundي حد ڪانه ھجي. پاڙ پاڻ کي کاٻي يا سا boundي سرحد طور سمجهيو ويندو آهي. هتي هڪ شرط اها به آهي ته جيڪڏهن اسان حد بندي نوڊس کي پرنٽ ڪيون ، اسان کي ڌيان ڏيڻ جي ضرورت آهي ته ٻن نوڊن مان ڪو به ڪيترائي دفعا ڇپيل نه آهي.

مسئلو حل ڪرڻ لاءِ اسين وڻ جي کاٻي حد سان شروعات ڪنداسين. اسان اهو چئون ٿا ته هڪ نوڊ کاٻي حد تائين تعلق آهي جيڪڏهن اهو نوڊ کاٻي پاسي کان ظاهر ٿئي ٿو. ساڳي طرح ، اسان صحيح طرف جوڙيندڙ ۽ پتي نوڊس جي وضاحت ڪيون ٿا. کاٻي حد کي پرنٽ ڪرڻ لاءِ ، اسين وڻ کي انهيءَ طريقي سان پار ڪري رهيا آهيون ته جيڪڏهن روٽ کي کاٻي نوڊ آهي ته پوءِ ان کي منتقل ڪرڻ جي لاءِ ان جي سا rightي نوڊ ڏانهن. هڪ دفعو اسين پتي نوڊ ڏانهن ايندا. اسين پتي نوڊس کي پرنٽ نٿا ڪريون ڇاڪاڻ ته اسين پتيءَ نوڊس کي ڌار ڌار ڇپائيندا آهيون. هڪ دفعو اسان کي کاٻي ڌر سان مڪمل ڪيو ويو آهي.

اسان پيسٽ نوڊس کي پرنٽ ڪندا آهيون ، سڌارن سان پهرين ڇپائي بائیں سبيري پٽن کي. کاٻي پاسي ڇپائڻ کان پوءِ سبيري leavesٽن کي پرنٽ ڪري سا theي سبري ۾ ڇڏي ٿو. اھڙي طرح سڀني پتي نوڊس کي گھڙي وار مخالف طرف ۾ ڇپايو ويندو۔ هڪ دفعو اسين پنن کي پرنٽ ڪندا آهيون ، اسين صحيح حد جي نوڊس ڇڪيندا آهيون. هن وقت نوٽس کي هيٺئين طريقي سان پرنٽ ڪرڻ جي ضرورت آهي. اهڙيءَ ريت اندر مفاهمتپهرين حل ڪريون ٿا وڻ جي کاٻي يا سا subي سبزيڊ ۽ پوءِ پي ايم ڪراٽ موجوده نوڊ.

بائنري وڻ جي Boundary Traversal پرنٽ ڪرڻ لاءِ C ++ ڪوڊ

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

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

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

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

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);
  root->left->right->right = create(4);

  boundaryUtil(root);
}
5 7 9 1 4 3

بائنري وڻ جي بائونڊري ٽريولر کي پرنٽ ڪرڻ لاءِ جاوا ڪوڊ

import java.util.*;

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

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

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

  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);
    root.left.right.right = create(4);

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

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

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

اي (اين) ، ڇاڪاڻ ته اسان وڻ جي سڀني نوڊن مان گذري چڪا آهيون. جڏهن اسان پرنٽ ليفٽ ، پرنٽ رائيٽ ، ۽ پرنٽ ليفن فنڪشن کي استعمال ڪندا آهيون ته نوڊس ذريعي سفر ڪريون ٿا. ان ڪري وقت جي پيچيدگي سڌي آهي.

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

اي (ايڇ) ، جتي H وڻ جي اوچائي آهي. اهو ئي سبب آهي ته مرتب ڪندڙ اسٽيڪ جاءِ استعمال ڪندو آهي. ۽ افعال حد بندي ٿيل عناصر کي پرنٽ ڪرڻ لاءِ استعمال ڪندا آهن جيڪي تاليف وارا اسٽيڪ جي ڳڻپ ڪندا آهن.