3.2.29 #
解答 #
本题在原书后续印刷中已修改，这里仍采用中文版的题目。
部分解答：https://algs4.cs.princeton.edu/32bst/BST.java.html（isSizeConsistent()）
如果根结点记录的结点数=左子树的结点数+右子树的结点数+1，就符合要求。
按照这个题意编制递归方法即可。
先写边界，当输入为 null 时，显然符合要求。
然后计算左子树的 Size 和右子树的 Size 加起来是否等于根结点的 Size + 1，
以及左子树和右子树是否符合同样的条件。
代码 #
protected static bool IsBinaryTree(Node x)
{
if (x == null)
{
return true; // 空树显然符合二叉树条件。
}
var size = 1; // 包括当前结点本身。
if (x.Left != null)
{
size += x.Left.Size;
}
if (x.Right != null)
{
size += x.Right.Size;
}
return IsBinaryTree(x.Left) &&
IsBinaryTree(x.Right) &&
x.Size == size;
}