หาความสูงของ Special Binary Tree ที่ Leaf เชื่อมเป็น Circular DLL ใน C++

Special Binary Tree: Leaf Nodes เชื่อมต่อกันเป็น Circular Doubly Linked List (Left = Prev, Right = Next)

หาความสูง (Height) ของต้นไม้

การตรวจสอบ Leaf Node

ในต้นไม้ทั่วไป Leaf = Left==NULL && Right==NULL
แต่ที่นี่ Leaf มี Pointer ชี้ Leaf อื่น → ตรวจสอบว่า:

node->left && node->left->right == node &&
node->right && node->right->left == node

ตัวอย่างโค้ด

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

    // เชื่อม Leaf เป็น Circular DLL: 6, 5, 3
    Node *L1 = root->left->left->left; // 6
    Node *L2 = root->left->right;      // 5
    Node *L3 = root->right;            // 3

    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);
    return 0;
}

ผลลัพธ์

Height of tree is: 4

โครงสร้างต้นไม้

       1
      / \
     2   3 (Leaf)
    / \
   4   5 (Leaf)
  /
 6 (Leaf)

Leaf: 6, 5, 3 → เชื่อมเป็น Circular DLL
Height = 4 (Path: 1-2-4-6)