C++에서 이진 탐색 트리의 Inorder Successor를 찾는 프로그램

이진 탐색 트리 BST와 노드의 다른 값이 있다고 가정하면 BST에서 해당 노드의 순서대로 후속 작업을 찾아야 합니다. 우리 모두는 노드 p의 후임자가 p 값보다 큰 가장 작은 키를 가진 노드라는 것을 알고 있습니다.

따라서 입력이 다음과 같으면

그리고 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;
}

입력

TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
1

출력

2