查找其叶子节点在C ++中连接的特殊二叉树的高度
假设我们有一棵特殊的二叉树，其叶节点被连接起来形成一个循环的双向链表。我们必须找到它的高度。因此，最左边的叶子的左指针将充当圆形双链表的前一个指针，而其右指针将充当链表的下一个指针。
在这种情况下，高度查找策略类似于普通的二叉搜索树。我们递归地计算节点左右子树的高度，并为该节点分配两个孩子的最大值max+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