3.2.29

上次更新:2019-10-06
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

本题在原书后续印刷中已修改,这里仍采用中文版的题目。

部分解答: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;
}

另请参阅

BinarySearchTree 库

上一题 下一题