ພິມມຸມມອງຂວາຂອງຕົ້ນໄມ້ຖານສອງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Adobe Amazon MakeMyTrip Snapdeal
ຕົ້ນໄມ້ຖານສອງ ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ Print Right View of Binary Tree” ລະບຸວ່າທ່ານໄດ້ຮັບຕົ້ນໄມ້ຖານສອງ. ໃນປັດຈຸບັນທ່ານຈໍາເປັນຕ້ອງຊອກຫາທັດສະນະທີ່ຖືກຕ້ອງຂອງຕົ້ນໄມ້ນີ້. ຢູ່ທີ່ນີ້, ມຸມມອງທີ່ຖືກຕ້ອງຂອງຕົ້ນໄມ້ໄບນາລີ ໝາຍ ເຖິງການພິມ ລຳ ດັບຕາມທີ່ຕົ້ນໄມ້ເບິ່ງເມື່ອເບິ່ງຈາກທິດທາງທີ່ຖືກຕ້ອງ.

ຍົກຕົວຢ່າງ

ພິມມຸມມອງຂວາຂອງຕົ້ນໄມ້ຖານສອງ

2 7 4 6

ຄໍາອະທິບາຍ

ຖ້າທ່ານສັງເກດເຫັນຕົ້ນໄມ້ຖານສອງໃນທາງທີ່ຖືກຕ້ອງ. ພວກເຮົາສາມາດເຫັນພຽງແຕ່ຂໍ້ທີ່ຖືກຕີພິມໃນຜົນໄດ້ຮັບ. ເນື່ອງຈາກວ່າຂໍ້ 3 ແລະ 5 ໄດ້ເຊື່ອງຊ້ອນຢູ່ຫລັງ 7 ແລະ 4 ຕາມ ລຳ ດັບ.

ວິທີການເພື່ອພິມພາບທີ່ຖືກຕ້ອງຂອງຕົ້ນໄມ້ຖານສອງ

ໃນບັນຫານີ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາທັດສະນະທີ່ຖືກຕ້ອງຂອງ ໜັງ ສືພິມ ຕົ້ນໄມ້ຖານສອງ. ບັນຫາສາມາດແກ້ໄຂໄດ້ໂດຍໃຊ້ສອງວິທີ. ໜຶ່ງ ໃນນັ້ນໃຊ້ແຖວແລະອີກອັນ ໜຶ່ງ ໃຊ້ການເອີ້ນຄືນ. ກ່ອນອື່ນ ໝົດ, ພວກເຮົາຈະປຶກສາຫາລືກ່ຽວກັບວິທີການ ນຳ ໃຊ້ແຖວ. ສະນັ້ນ, ເພື່ອແກ້ໄຂບັນຫາໂດຍໃຊ້ a ຄິວ. ພວກເຮົາເລີ່ມຕົ້ນຈາກຮາກຂອງຕົ້ນໄມ້ຖານສອງ. ສຳ ລັບແຕ່ລະລະດັບຂອງຕົ້ນໄມ້, ພວກເຮົາສືບຕໍ່ເກັບຮັກສາຂໍ້ທີ່ຢູ່ໃນແຖວ. ສຳ ລັບການເກັບຮັກສາຂໍ້ຂອງຂໍ້ຕໍ່ໄປ, ພວກເຮົາຕ້ອງໄດ້ຂ້າມຜ່ານຂໍ້ຂອງລະດັບປັດຈຸບັນ. ສະນັ້ນເມື່ອພວກເຮົາ ກຳ ລັງຜ່ານເສັ້ນທາງຂອງລະດັບປັດຈຸບັນ. ພວກເຮົາພິມ node ສຸດທ້າຍໃນລະດັບນີ້. ເມື່ອພວກເຮົາສັງເກດເຫັນຕົ້ນໄມ້ຈາກເບື້ອງຂວາ. Node ດຽວທີ່ສາມາດເບິ່ງເຫັນໄດ້ຈາກພວກເຮົາແມ່ນຂໍ້ທີ່ຖືກຕ້ອງທີ່ສຸດໃນລະດັບ ໜຶ່ງ. ວິທີການນີ້ໃຊ້ແຖວທີ່ໃຊ້ເວລາຫວ່າງ.

ຂໍໃຫ້ປຶກສາຫາລືກ່ຽວກັບວິທີແກ້ໄຂໂດຍໃຊ້ການເອີ້ນຄືນ. ວິທີແກ້ໄຂແມ່ນຄ້າຍຄືກັນກັບການຊອກຫາມຸມເບິ່ງເບື້ອງຊ້າຍຂອງຕົ້ນໄມ້. ໃນວິທີການນີ້. ພວກເຮົາພຽງແຕ່ເຮັດ traversal ຂອງຕົ້ນໄມ້ທີ່ກົງກັນຂ້າມກັບຂອງ traversal inorder ໄດ້. ແຕ່ພວກເຮົາຍັງຕິດຕາມລະດັບທີ່ພວກເຮົາຢູ່ໃນປະຈຸບັນແລະລະດັບສູງສຸດທີ່ບັນລຸໄດ້ຈົນເຖິງປະຈຸບັນ. ດັ່ງທີ່ພວກເຮົາຍ້າຍໄປຢູ່ໃນລັດຖະບັນຍັດເບື້ອງຂວາກ່ອນທີ່ຈະມີລັດຖະບັນຍັດເບື້ອງຊ້າຍ. ທຸກຄັ້ງທີ່ພວກເຮົາເຂົ້າສູ່ລະດັບ ໃໝ່ ໃນຕົ້ນໄມ້. ພວກເຮົາພົບກັບຂໍ້ທີ່ຖືກຕ້ອງທີ່ສຸດ. ສະນັ້ນພວກເຮົາຮັກສາການກວດກາຢູ່ສະ ເໝີ ຖ້າລະດັບປະຈຸບັນສູງກວ່າລະດັບສູງສຸດ, ພວກເຮົາພິມ node. ວິທີການຈະດີກວ່າຖ້າພວກເຮົາບໍ່ພິຈາລະນາເຖິງພື້ນທີ່ທີ່ ຈຳ ເປັນ ສຳ ລັບການລວບລວມຂໍ້ມູນ. ຄວາມສັບສົນຂອງພື້ນທີ່ ສຳ ລັບບັນຫາແມ່ນຂື້ນກັບລະດັບຄວາມສູງຂອງຕົ້ນໄມ້ຖ້າພວກເຮົາພິຈາລະນາພື້ນທີ່ທີ່ປະຕິບັດໂດຍເພກລວບລວມ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອພິມຂວາມືຂອງ Binary Tree

#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;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

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

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

ລະຫັດ Java ເພື່ອພິມຂວາມືຂອງ Binary Tree

import java.util.*;

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

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

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  public static void main(String[] args){
    node root = create(2);
    root.left = create(3);
    root.right = create(7);
    root.left.left = create(5);
    root.left.right =create(4);
    root.left.right.left = create(6);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ພວກເຮົາ ກຳ ລັງຂ້າມຜ່ານຂໍ້ຂອງຕົ້ນໄມ້. ສະນັ້ນຖ້າມີ Nodes ຢູ່ໃນຕົ້ນໄມ້, ລະບົບ algorithm ຮຽກຮ້ອງໃຫ້ມີການ ດຳ ເນີນງານ O (N).

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1). ຖ້າພື້ນທີ່ໃຊ້ໂດຍ stack compiler ບໍ່ໄດ້ຖືກພິຈາລະນາ, ອື່ນ O (H) ຕ້ອງມີພື້ນທີ່