在给定树中查找最大的完美二叉树

当二叉树中存在的所有节点至少有两个子节点，并且所有叶子节点都处于同一层或阶段时，通常认为它是完美的二叉树。

为了找到最大的完美二叉树，我们可以使用 DFS 方法。

1. 在这种技术中，我们必须从二叉树的根开始。
2. 在每个给定节点处，我们必须确保其左右子树是完美的二叉树。
3. 为了确保每棵树都是完美的二叉树，我们必须观察子树中的节点数是否是 2 的幂。我们可以通过计算任何其他遍历中的节点数来做到这一点。
4. 如果我们遇到一个看起来是完美二叉树的子树，我们必须更新我们找到的二叉树的最大大小。
5. 我们将重复此过程，直到我们遍历了二叉树中的所有节点。
6. 我们必须返回到目前为止找到的完美二叉树的大小。

实施

输出

代码的分步解释

1. 代码首先包含必要的头文件，包括 bits/stdc++.h>，其中包含所有标准 C++ 库。
2. 接下来，我们定义二叉树中的一个节点结构，其中包含各种数据。
3. 我们创建一个名为“new node”的函数，它基本上帮助我们定义新数据，并且还帮助我们为节点分配内存并初始化其成员。
4. 我们定义另一个名为“returnType”的结构，它主要关注完美二叉树函数的类型。它包含三个成员：height、isPerfect 和 rootTree。
5. 函数 findPerfectBinaryTree 通常将根节点作为函数，然后搜索以在其范围内找到最大的完美二叉树。
6. 在这个函数内部，我们首先检查基本情况，这有助于我们在发现根为 NULL 时。然后它被认为是高度为 0 的完美二叉树。
7. 如果未满足主要情况，则函数将为当前节点的左子节点和右子节点调用 findPerfectBinaryTree。
8. 接下来，左子树的结果存储在 lv 中，右子树的结果存储在 rv 中。
9. 然后函数验证两个子树是否都完美且高度相同。如果满足此条件，则意味着当前根节点也是完美的。在这种情况下，子树的高度设置为 lv.height + 1，isPerfect 设置为 true，rootTree 设置为当前根。我们必须等到结果返回。
10. 如果未满足步骤 9 中的条件，则意味着当前子树不完美。
11. 现在，在程序的主要函数中，我们创建 NewNode 来设置它们的左右指针。
12. 调用 findPerfectBinaryTree 函数并传入二叉树的根，结果存储在名为“ans”的变量中。

示例 2)

输出

代码的分步解释

1. 代码通常在第一步导入必要的 Java util 类。
2. 然后代码定义了一个名为 TPT 的类，其中包含程序的主要逻辑。
3. 接下来，代码定义了一个名为“node”的静态嵌套类，它表示树的节点结构，每个节点都包含一个整数值以及对其左右子节点的引用。
4. 然后我们通过创建一个名为“newnode”的方法来创建一个新节点，该方法使用给定数据值创建一个新节点，将左右子节点初始化为 NULL，并返回创建的节点。
5. 我们通过定义另一个名为“returnType”的静态方法来表示 findPerfectBinaryTree 函数的 returnType 结构。它主要包含三个字段：isPerfect、Height 和 rootTree。
6. 现在，使用 findPerfectBinaryTree 方法，它将节点对象作为输入，递归地找出最大的二叉树，并返回一个将保存结果的 returnType。
7. 代码将递归调用 findPerfectBinaryTree 函数，用于当前节点的左子节点和右子节点。
8. 现在代码将验证左右子树是否是完美的二叉树并且具有相同的高度。如果满足此条件，则当前子树也是完美的二叉树，并且该函数会使用高度和根数据更新“rt”对象并返回它。
9. 如果当前子树不是完美的，那么 isPerfect 返回 false 值。然后我们评估左右子树之间的最大高度，将最大高度的子树的根作为根，并返回“rt”对象。
10. 接下来，我们定义另一个名为“inorder-print”的静态方法，它执行二叉树的中序遍历并打印节点值。
11. 最后，程序的主要函数无疑是程序的入口点。它通常创建一个包含六个节点的二叉树并将其分配给根变量。然后它执行所有函数并提供必要的结果。

结论

上面提供的方法是一种实现，用于在给定树中找出最大的完美二叉树。主要结论是代码使用各种函数和指针来有效地找到可能的二叉树，然后以中序遍历的方式打印其大小。