检查二叉搜索树是否退化

Question

我想检查二叉搜索树是否退化（它是链表还是树？）我确实提出了一个非递归解决方案，我认为它非常聪明，但规范规定它必须是一个递归解决方案，我正在将它从非递归转换为递归。

这是我的非递归解决方案（实际上并不是因为大小和高度都是递归实现的。但是这种方法不是）。

public boolean isDegenerate(){
        if(this.size() == this.getHeight()){
            return true;
        }
        return false;
    }

Answer 1

好吧，如果你想要一个“更递归”的解决方案，这个怎么样？

public boolean isDegenerate() {
    if (this.left != null) {
        if (this.right != null) {
            return false; // not degenerate, has two children
        } else {
            return this.left.isDegenerate();
        }
    } else {
        if (this.right != null) {
            return this.right.isDegenerate();
        } else {
            return true; // we arrived at the bottom without seeing any node with two children
        }
    }
}