Người kế vị Inorder trong BST bằng C ++

Giả sử chúng ta có một cây tìm kiếm nhị phân và một nút trong đó, chúng ta phải tìm kiếm kế thừa theo thứ tự của nút đó trong BST. Như chúng ta biết rằng nút kế thừa của nút p là nút có khóa nhỏ nhất lớn hơn p.val.

Vì vậy, nếu đầu vào là root =[2,1,3], p =1,

thì đầu ra sẽ là 2,

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa phương thức đệ quy inorderSuccessor (), phương thức này sẽ có gốc và p

• nếu root null thì -

  • trả về null

• if val of root <=val of p, then -

  • return inorderSuccessor (bên phải của thư mục gốc, p)

• Nếu không

  • option:=inorderSuccessor (bên trái của thư mục gốc, p)

  • return (nếu tùy chọn bằng 0 thì hãy root, nếu không tùy chọn)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
public:
   TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
      if(!root) return NULL;
      if(root->val <= p->val){
         return inorderSuccessor(root->right, p);
      }
      else{
         TreeNode* option = inorderSuccessor(root->left, p);
         return !option ? root : option;
      }
   }
};
main(){
   TreeNode *root = new TreeNode(2);
   root->left = new TreeNode(1);
   root->right = new TreeNode(3);
   TreeNode *p = root->left;
   Solution ob;
   cout << (ob.inorderSuccessor(root, p))->val;
}

Đầu vào

{2,1,3},1

Đầu ra

2