使用C ++的给定高度的AVL树中的最小节点数。

问题陈述

给定AVL树的高度，任务是找到该树可以具有的最小节点数。

If height = 0 then AVL tree can have one 1 node
If height = 5 then AVL tree can have minimum 20 nodes

算法

在AVL树中，我们必须保持高度平衡属性，即，每个子节点的左右子树的高度差不能超过-1、0或1。使用此属性，我们可以创建以下递归关系：

1. If height = 0 then return 1
2. If height = 1 then return 2
3. If height > 1 then return (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))

示例

#include <iostream>
using namespace std;
int getMinAVLNodes(int h){
   if (h < 0) {
      return 0;
   }
   if (h == 0 || h == 1) {
      return h + 1;
   }
   return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2);
}
int main(){
   int h = 5;
   cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它生成以下输出-

Minimum nodes for 5 height = 20