Inorder Successor ຂອງ node ໃນ Binary Tree


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon Expedia Morgan Stanley ຫ້ອງ OYO SnapChat
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ຕົ້ນໄມ້

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

ບັນຫາຂໍໃຫ້ຊອກຫາ“ Inorder Successor ຂອງຂໍ້ໃນຕົ້ນໄມ້ຖານສອງ”. ຜູ້ສືບທອດທາງອິນເຕີເນັດຂອງ node ແມ່ນຂໍ້ທີ່ຢູ່ໃນຕົ້ນໄມ້ຖານສອງທີ່ມາຫຼັງຈາກ node ທີ່ຢູ່ໃນເສັ້ນທາງຂວາງຂອງຕົ້ນໄມ້ຖານສອງທີ່ໃຫ້.

ຍົກຕົວຢ່າງ

Inorder successor of 6 is 4

ຄໍາອະທິບາຍ

ການປ່ຽນເສັ້ນທາງຂອງຕົ້ນໄມ້ແມ່ນ 9 7 1 6 4 5 3. ດັ່ງນັ້ນຜູ້ສືບທອດ inorder ຂອງ 1 ແມ່ນ 6.

ວິທີການ

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

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

ໃນປັດຈຸບັນກໍລະນີສຸດທ້າຍແມ່ນຖ້າ node ແມ່ນເດັກທີ່ຖືກຕ້ອງທີ່ສຸດ. ຖ້າສິ່ງນັ້ນເກີດຂື້ນກໍ່ບໍ່ມີຜູ້ສືບທອດອິນເຕີເນັດ ສຳ ລັບ node.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາ Inorder Successor ຂອງ node ໃນ 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;
}

node* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

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);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

ລະຫັດ Java ເພື່ອຊອກຫາ Inorder Successor ຂອງ node ໃນ Binary Tree

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 findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  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);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

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

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

O (N), ເພາະວ່າໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດພວກເຮົາອາດຈະຕ້ອງຂ້າມຜ່ານທຸກຂໍ້.

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

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