C++에서 리프 노드가 연결된 특수 이진 트리의 높이 찾기

리프 노드가 연결되어 순환 이중 연결 목록을 형성하는 특수 이진 트리가 있다고 가정합니다. 우리는 그 높이를 찾아야 합니다. 따라서 맨 왼쪽 리프의 왼쪽 포인터는 원형 이중 연결 목록의 이전 포인터 역할을 하고 오른쪽 포인터는 연결 목록의 다음 포인터 역할을 합니다.

이 경우 높이 찾기 전략은 일반 이진 탐색 트리와 유사합니다. 우리는 재귀적으로 노드의 왼쪽 및 오른쪽 하위 트리의 높이를 계산하고 노드에 대한 높이를 두 자식의 최대값 + 1로 할당합니다. 하지만 여기서 잎은 원형 이중 연결 목록의 요소입니다. 따라서 노드가 리프 노드가 되려면 노드 왼쪽의 오른쪽이 노드를 가리키고 오른쪽의 왼쪽이 노드 자체를 가리키는지 확인합니다.

예시

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
      Node *left, *right;
};
bool isLeafNode(Node* node) {
   return node->left && node->left->right == node && node->right && node->right->left == node;
}
int findHeight(Node* node) {
   if (node == NULL)
      return 0;
   if (isLeafNode(node))
      return 1;
   return 1 + max(findHeight(node->left), findHeight(node->right));
}
Node* getNode(int data) {
   Node* node = new Node;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}
int main() {
   Node* root = getNode(1);
   root->left = getNode(2);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(5);
   root->left->left->left = getNode(6);
   Node *L1 = root->left->left->left;
   Node *L2 = root->left->right;
   Node *L3 = root->right;
   L1->right = L2, L2->right = L3, L3->right = L1;
   L3->left = L2, L2->left = L1, L1->left = L3;
   cout << "Height of tree is: " << findHeight(root);
}

출력

Height of tree is: 4