C++のBSTのInorderSuccessor

二分探索木とその中にノードがあるとすると、BSTでそのノードの順序どおりの後続を検索する必要があります。ノードpの後継は、p.valより大きい最小のキーを持つノードであることがわかっています。

したがって、入力がroot =[2,1,3]、p =1、

その場合、出力は2になります

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

• 再帰的メソッドをinorderSuccessor（）で定義します。これにより、ルートとp

  が取得されます。

• ルートがnullの場合、-

  • nullを返す

• ルートのval<=pのvalの場合、-

  • inorderSuccessor（ルートの権利、p）を返す

• それ以外の場合

  • オプション：=inorderSuccessor（ルートの左側、p）

  • return（オプションがゼロの場合はルート、それ以外の場合はオプション）

例

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

#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