algorithm - 是否有解决 `size` 或 `height` 的二叉树问题的技巧？

Question

关于二叉树，我理解size和height的区别:size是节点数而 height of a tree 是从根到最远叶子的最大边数。

但是，在处理涉及高度的问题时，我的脑子经常是扭曲的，想不通。

对于以下两个问题，它们非常相似，只是一个限制了size，而另一个限制了height。

---

例如，让我们先来看看涉及size的那个。

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function to construct all possible completely balanced binary trees for a given number of nodes - n. The function should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

本题是生成所有可能的完全平衡的二叉树，只要满足该性质。

我认为 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，则返回一个只有一个单例内部节点和两个叶子的集合。

---

当题目中的size改成height时，我真的不知道怎么再巧妙地思考了。

In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Write a function to construct all possible height-balanced binary trees for a given number of nodes - n. The function should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

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

---

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

我究竟应该如何训练自己来处理高度问题？诀窍在哪里？

Answer 1

不，这不一样。考虑:(每个节点的值表示其子树的高度)

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

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

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

然后你需要遍历左子树和右子树的高度(这将是左子树的高度 + 1/0/-1)，如果我们可以得到 n使用这些高度，即:这些高度加一的最大节点数是>= n这些高度加一的最小节点数是<= n , 遍历所有加起来为 n 的组合，生成所有有效的树，并合并它们，类似于您对第一个问题所做的。

我希望这是有道理的。

---

处理涉及高度的问题没有真正的诀窍 - 方法因问题而异。通常重要的是要记住平衡树的高度是 ~log<sub>2</sub>n还有一棵完整的高度树n有2^n-1节点。