C++のBSTIIの後継者

二分探索木にノードがあるとすると、BSTでそのノードの順序どおりの後続ノードを見つける必要があります。順序どおりの後続がない場合は、nullを返します。ノードの後継は、ノードの値よりも小さいキーを持つノードであることがわかっています。

ノードには直接アクセスできますが、ツリーのルートにはアクセスできません。ここで、各ノードはその親ノードへの参照を持ちます。以下はノードの定義です-

class Node {
   public int val;
   public Node left;
   public Node right;
   public Node parent;
}

入力が-

ノードが2の場合、出力は3になります。

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

• ノードの権利がnullでない場合、-

  • ノード：=ノードの右側

  • ノードの左側がnullでない場合は、-

    を実行します。

    • ノード：=ノードの左側

  • リターンノード

• 一方（ノードの親がnullでなく、ノードがノードの親の左側と等しくない）、do-

  • node：=ノードの親

• リターンノードの親

例

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

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* parent;
   Node(int v, Node* par = NULL){
      val = v;
      left = NULL;
      right = NULL;
      parent = par;
   }
};
class Solution {
public:
   Node* inorderSuccessor(Node* node) {
      if (node->right) {
         node = node->right;
         while (node->left)
         node = node->left;
         return node;
      }
      while (node->parent && node != node->parent->left) {
         node = node->parent;
      }
      return node->parent;
   }
};
main(){
   Solution ob;
   Node *root = new Node(5);
   root->left = new Node(3, root);
   root->right = new Node(6, root);
   root->left->left = new Node(2, root->left);
   root->left->right = new Node(4, root->left);
   root->left->left->left = new Node(1, root->left->left);
   cout << (ob.inorderSuccessor(root->left->left))->val;
}

入力

Node *root = new Node(5);
root->left = new Node(3, root);
root->right = new Node(6, root);
root->left->left = new Node(2, root->left);
root->left->right = new Node(4, root->left);
root->left->left->left = new Node(1, root->left->left);
(ob.inorderSuccessor(root->left->left))->val

出力

3