查询叶节点在 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

更新日期： 2019 年 12 月 17 日

166 次浏览

开启你的 职业

完成课程结业，获得认证

开始
广告