C++でバイナリ検索ツリーのInorderSuccessorを検索するプログラム

二分探索木BSTとノードの別の値があるとすると、BSTでそのノードの順序どおりの後続を見つける必要があります。ノードpの後継は、pの値よりも大きい最小のキーを持つノードであることは誰もが知っています。

したがって、入力が次のような場合

そして、p =1の場合、出力は2になります

これを解決するには、次の手順に従います-

• 再帰的メソッドinorderSuccessor（）を定義します。これは、ルートとpを取得します
• ルートがnullの場合、次のようになります。
  • nullを返す
• ルートの値<=pの値の場合：
  • return inorderSuccessor（rootの権利、p）
• それ以外の場合
  • option：=inorderSuccessor（rootの左側、p）
  • return（オプションがゼロの場合はroot、それ以外の場合はオプション）

理解を深めるために、次の実装を見てみましょう-

例

#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