Tìm chiều cao cây nhị phân đặc biệt có lá nối thành danh sách liên kết vòng trong C++

Cây nhị phân đặc biệt: các nút lá nối thành danh sách liên kết đôi vòng (con trỏ left của lá trái nhất làm prev, right làm next). Tìm chiều cao cây.

Chiều cao tính như BST thông thường: max(chiều cao trái, phải) + 1. Nhận diện lá: node->left->right == node && node->right->left == node.

Ví dụ

#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 = 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);
}

Kết quả

Height of tree is: 4