C++에서 BST의 중위 계승자

이진 검색 트리와 그 안에 노드가 있다고 가정하고 BST에서 해당 노드의 순서대로 후속 항목을 검색해야 합니다. 노드 p의 후임자가 p.val보다 큰 가장 작은 키를 가진 노드라는 것을 알고 있기 때문입니다.

따라서 입력이 root =[2,1,3], p =1,

그러면 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 재귀 메서드 inorderSuccessor()를 정의합니다. 이것은 루트를 취하고 p

• 루트가 null이면 -

  • null 반환

• 루트의 val <=p의 val이면 -

  • inorderSuccessor(root의 오른쪽, p)를 반환

• 그렇지 않으면

  • 옵션 :=inorderSuccessor(루트 왼쪽, p)

  • 반환(옵션이 0이면 루트, 그렇지 않으면 옵션)

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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

입력

{2,1,3},1

출력

2