java - Return 语句无法从循环中正常工作

Question

我正在从事一个涉及平衡二叉树的项目，但遇到了一些问题。

对于我项目的一部分，我想查看一棵树(或子树)并比较所述子树左子树路径和右子树路径的最大长度。如果这些路径的最大长度之间的绝对差大于 1，我想返回找到的第一个具有此属性的节点。逻辑有点简单..例如，如果我有树:

我的算法将查看 64 并比较左侧和右侧路径的长度(分别为 5 和 4)。这不会创建一个标志，因为差异是 1。然后我会递归地查看 64 的 child 。首先它会查看 43，然后转到 26。在 26 之后(因为它的每个子节点到叶子的长度为 1)算法将移动到 62。此时将抛出一个标志，因为 62s 的左路径有一个长度3 并且它没有正确的路径。这是我想退出循环并返回 62 的地方。但是，我的循环会继续运行，直到它检查最终节点。

如您所见，算法继续运行并返回一个空节点，而不是我想要的节点。我不确定它为什么这样做，但我认为它与优先级和范围有关。具体算法代码如下:

    public BinaryNode<Integer> NodeCheck(BinaryNode<Integer> Node) throws IllegalStateException
    {
        System.out.println("CHECKING NODE: " + Node.getData());

        int leftHeight = 0;
        int rightHeight = 0;

        if (Node.hasLeft())
        {
            leftHeight = 1 + findHeight(Node.getLeft());
        }

        if (Node.hasRight())
        {
            rightHeight = 1 + findHeight(Node.getRight());
        }
        System.out.println("LEFT HEIGHT = " + leftHeight);
        System.out.println("RIGHT HEIGHT = " + rightHeight);

        int z = Math.abs(leftHeight - rightHeight);
        if (z > 1)
        {
            System.out.println();
            System.out.println();
            System.out.println("PROBLEM DETECTED AT NODE " + Node.getData() + " ATTEMPTING TO RETURN NODE");
            BinaryNode<Integer> flag = createNode(Node.getData(), Node.getParent(),Node.getLeft(), Node.getRight());

            return flag;
        }

        for (BinaryNode<Integer> c : children(Node))
            {
                if (findHeight(c) > 1 && z<= 1)
                    {NodeCheck(c);}
            }


        return createNode(0,null,null,null);

    }

我认为重要的是要注意，我最终处理了 if (z > 1) 语句中的信息，因为执行了 System.out.println() 语句，这让我相信 return 语句已执行。但是，这并没有像我假设的那样退出函数。

Answer 1

问题是，您递归调用此方法，但没有进行检查。

您应该更改以下内容以使其工作:

• 最终的返回应该返回null。
• 在之前的循环中，您应该检查返回值，如果它不是null，则返回它。

所以你方法的最后一部分应该是这样的:

    for ( final BinaryNode<Integer> c : children( node ) )
    {
        if ( findHeight( c ) > 1 && z <= 1 )
        {
            final BinaryNode<Integer> res = nodeCheck( c );
            if ( null != res )
                return res;
        }
    }
    return null;
}

运行它会产生这个输出:

CHECKING NODE: 64
LEFT HEIGHT = 5
RIGHT HEIGHT = 4
CHECKING NODE: 43
LEFT HEIGHT = 3
RIGHT HEIGHT = 4
CHECKING NODE: 26
LEFT HEIGHT = 2
RIGHT HEIGHT = 2
CHECKING NODE: 62
LEFT HEIGHT = 3
RIGHT HEIGHT = 0


PROBLEM DETECTED AT NODE 62 ATTEMPTING TO RETURN NODE