java - Java中二叉树的递归检查

Question

这是以下 Java 谜题 ( http://code-exercises.com/programming/medium/28/strict-binary-tree-check ) 中的一个小问题。任务是编写一个方法来检查给定二叉树中的所有节点是否具有 0 个或 2 个子节点。

他们的解决方案如下

public Boolean isStrictTree(TreeNode node) {
    if (node == null) {return true;}
    if ((node.left() == null && node.right() != null) || (node.left() != null && node.right() == null)) {return false;}

    return isStrictTree(node.left()) && isStrictTree(node.right());
}

我想出了类似的东西，但它不起作用。区别在于

a) 第一行 - 处理 null 情况(返回“null”而不是“true”)

b)递归的结构 - 我的递归结构以某种方式混杂在一起(如果我追踪一张纸上发生的情况，这种方式应该有效)，而不是将其分散在两行上的解决方案 - 条件和返回语句。

public Boolean isStrictTree(TreeNode node) {
    if (node == null) {return null;}

    else if ((isStrictTree(node.left()) == true) && (isStrictTree(node.right())==null)) {return false;}

    return true;
}

脚本运行但不返回任何内容。我真的很想了解为什么它不起作用，似乎我可以在这里学到一些东西，所以任何见解都会受到赞赏。

Answer 1

您有两个选择:要么节点有效/平衡，然后返回 true，要么节点无效/不平衡，返回 false。为什么要引入第三种状态 - null？不需要那个东西。

为什么它不起作用:在 (isStrictTree(node.left()) == true 中，对 isStrictTree(...) 的调用将返回 null 在某个时间点，因此当将其与 true 进行比较时，您会得到 NullPointerException。