查找为了使二叉树平衡而必须添加的最少节点数？

Question

假设给定了一个任意的二叉树。如果对所有节点都满足以下条件，则我们将树称为balanced：

1. 该节点是叶子，或
2. [左子树的高度和右子树的高度相差最多±1，并且左右子树本身是平衡的。

是否有一种有效的算法来确定需要添加到树中以使其平衡的最小节点数？为简单起见，我们假设节点只能作为叶节点插入（就像将节点插入没有重新平衡的二叉搜索树中的方式一样）。

假设给定了一个任意的二叉树。如果对所有节点都满足以下条件，则我们将树称为平衡树：该节点是叶子，或者左子树的高度和...

Answer 1

以下树适合您的定义，尽管对我而言似乎不太平衡：

Answer 2

首先让我们找到每个节点的左子节点和右子节点的高度。

现在考虑树的根的高度是

Answer 3

这项工作会吗？

从顶部递归进行。如果节点A不平衡，请在短边添加节点B，并向节点B添加足够的左侧节点，直到节点A平衡为止。