ໃຫ້ຕົ້ນໄມ້ໄບນາລີ, ທ່ານຈະເອົາເຄິ່ງກົກທັງ ໝົດ ອອກໄດ້ແນວໃດ?


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon Microsoft PayU Snapdeal Synopsys Yahoo
ຕົ້ນໄມ້

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

ຍົກຕົວຢ່າງ

ໃຫ້ຕົ້ນໄມ້ໄບນາລີ, ທ່ານຈະເອົາເຄິ່ງກົກທັງ ໝົດ ອອກໄດ້ແນວໃດ?

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

ຄໍາອະທິບາຍ

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

ວິທີການ

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

ລະຫັດ

ລະຫັດ 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

ລະຫັດ Java ເພື່ອ ກຳ ຈັດຂໍ້ມູນເຄິ່ງຂໍ້ທັງ ໝົດ

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

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

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

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ຂ້າມຜ່ານຂໍ້ທັງ ໝົດ ໃນຕົ້ນໄມ້ຖານສອງ. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

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

ໂອ (H), ສູດການຄິດໄລ່ແມ່ນວິທີການຄິດໄລ່ຄືນ ໃໝ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຂື້ນກັບ stack compiler ເຊິ່ງໃນນັ້ນແມ່ນຂື້ນກັບລະດັບຄວາມສູງຂອງຕົ້ນໄມ້.