有没有解决“大小”或“高度”二叉树问题的技巧？

Question

关于二叉树，我了解size和高度之间的区别：size是节点数，而树的高度是从根到最远叶子的最大边数。

但是，在处理涉及<码>高 的问题时，我的思维往往是扭曲的，无法直截了当地思考。

对于以下两个问题，它们非常相似，除了一个对size有约束，而另一个对高度有约束。

例如，让我们先看看涉及size。

在完全平衡的二叉树中，每个节点都具有以下属性：其左侧子树中的节点数和右侧子树中的节点数几乎相等，这意味着它们的差异不大于1。

编写一个函数，为给定数量的节点（n）构造所有可能的完全平衡二叉树。该函数应通过回溯生成所有解。将字母“x”作为信息放入树的所有节点。

这个问题是生成所有可能的完全平衡二叉树，只要该属性保持不变。

我认为size很简单。我能做的是这样的：

1. 使用递归
2. 如果n mod 2=1，则使用n=n/2生成所有此类树，然后将每对树合并为一个新根。
3. 如果n mod 2=0，则生成一组带有n/2的树和另一组带有n/2-的树。然后将每对（来自集合的一个）与新根合并，也不要忘记交换每对内的元素。
4. 如果n=0，则返回一个只有一个叶子的集合
5. 如果n=1，则返回一个只有一个具有两个叶子的单例内部节点的集合。

当问题中的大小变为高度时，我真的不知道如何再聪明地思考了。

在高度平衡二叉树中，每个节点都具有以下特性：左子树的高度和右子树的高度几乎相等，这意味着它们的差值不大于1。

编写一个函数，为给定数量的节点（n）构造所有可能的高度平衡二叉树。该函数应通过回溯生成所有解。将字母“x”作为信息放入树的所有节点。

我认为如果涉及身高，事情会变得相当随意。

第二题的解法和第一题一样吗？

我真的应该如何训练自己来处理身高问题？诀窍在哪里？

Answer 1

不，不一样。考虑：（每个节点的值表示其子树的高度）

     4
   /   \
  2     3
 /     / \
1     2   2
     / \ / \
    1  1 1  1

左子树有2个节点，右子树有7个节点，但高度平衡。

您需要做的第一件事是计算某个给定高度的最小和最大节点数（最大值只是2^n-1，最小值可以从高度1开始迭代计算，或者可能还有一个公式）。

然后你需要循环左子树和右子树的高度（这将是左子树的高度1/0/-1），如果我们可以使用这些高度得到n，也就是说：这些高度的最大节点数加上一个是

我希望这是有道理的。

处理涉及身高的问题没有什么真正的诀窍——方法因问题而异。通常重要的是要记住，平衡树的高度是~log2n，一个完整的高度n树有2^n-1节点。