C++ 中平衡二叉树的数量

给定二叉树的高度 H。目标是找到给定高度的平衡二叉树的数量/计数。

二叉树 - 是一种树形数据结构，其中每个节点最多有两个子节点，分别是左子节点和右子节点。

高度平衡二叉树 - 定义为二叉树，其中每个节点的两个子树的深度之差仅为 1 或 0。即每个节点的左子树和右子树的高度差最大为 1。

下图包含了高度 h=3 的所有可能的平衡二叉树。

输入

Height H=2

输出

Count of Balanced Binary Trees of Height H is : 3

解释 - 给定图包含了高度 H=2 的所有可能的平衡树

输入

Height H=3

输出

Count of Balanced Binary Trees of Height H is : 15

下面程序中使用的思路如下

  • 整数 H 用于表示二叉树的高度。

  • 函数 countBTheight(int h) 以树的高度作为输入，并返回高度为 h 的所有可能的平衡二叉树的数量。

  • 我们使用递归方法。

  • 如果树的高度为 1，即它只有一个节点，则只有一个具有单个节点的树存在且它是平衡的。（if(h==1)，返回 1）

  • 否则，高度是左子树和右子树的高度之和，其高度比根节点小一或二。（平衡树的高度差为 1）。

  • 函数返回计数作为结果。

示例

 实时演示

#include <iostream>
int countBTheight(int h){
   // One tree is possible with height 0 or 1
   if (h == 0 || h == 1)
      return 1;
   return countBTheight(h-1) * (2 *countBTheight(h-2) + countBTheight(h-1));
}
int main(){
   int H = 4;
   std::cout << "Count of balanced binary trees of height H is: "<<countBTheight(H);
}

输出

Count of balanced binary trees of height H is: 315

更新于: 2020-07-28

339 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告