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

이진 탐색 트리에 노드가 있다고 가정하고 BST에서 해당 노드의 순차 계승자를 찾아야 합니다. 순서대로 계승자가 없으면 null을 반환합니다. 노드의 후임자는 노드의 값보다 큰 키가 가장 작은 노드라는 것을 알고 있기 때문입니다.

노드에는 직접 액세스할 수 있지만 트리 루트에는 액세스할 수 없습니다. 여기서 각 노드는 상위 노드에 대한 참조를 갖습니다. 아래는 Node −

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

입력이 다음과 같은 경우 -

노드가 2이면 출력은 3이 됩니다.

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

• 노드의 오른쪽이 null이 아니면 -

  • 노드 :=노드의 오른쪽

  • 노드의 왼쪽이 null이 아닌 동안 수행 -

    • 노드 :=노드의 왼쪽

  • 반환 노드

• 동안 (노드의 부모가 null이 아니고 노드가 노드의 부모의 왼쪽과 같지 않음) -

  • 노드 :=노드의 부모

• 반환 노드의 부모

예시

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

#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