java - 递归逻辑的调用堆栈在 java 中的行为不正确

Question

我正在编写一个程序来获取给定的深度总和binaryTree。如果我从方法中打印返回值，它会返回带有实例值的正确值，但返回错误值（大于预期）。带输出的代码如下。
注意：我也有正确的解决方案，但我发布此解决方案是为了了解递归调用堆栈有什么问题。我的期望是在最后一个堆栈内存中，最终值将持续存在，并将返回给返回不同值的调用方方法。

public class NodeDepth_2 {

    static int sum = 0;
    
    public static int nodeDepths(BinaryTree root) {
        Integer depthSum = 0;
        Integer depth = -1;
        int finalValue = nodeDepths(root, depth, depthSum);
        System.out.println("Printing returned value from method: " + finalValue);
        System.out.println("sum from instance variable : " + sum);
        return depthSum.intValue();

    }

    public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
        depth = depth + 1;
        depthSum = depthSum + depth;
        sum = sum + depth;


        if (root.left == null && root.right == null) {
            return depthSum;
        }

        return nodeDepths(root.left, depth, depthSum) + nodeDepths(root.right, depth, depthSum);

    }

    static class BinaryTree {

        int value;

        BinaryTree left;

        BinaryTree right;

        public BinaryTree(int value) {

            this.value = value;

            left = null;

            right = null;

        }

    }

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(1);

        root.left = new BinaryTree(2);

        root.left.left = new BinaryTree(4);
        root.left.left.left = new BinaryTree(8);

        root.left.left.right = new BinaryTree(9);

        root.left.right = new BinaryTree(5);

        root.right = new BinaryTree(3);

        root.right.left = new BinaryTree(6);

        root.right.right = new BinaryTree(7);

        nodeDepths(root);
    }

}

输出是：

Printing returned value from method: 21 // wrong value returned with method return
sum from instance variable : 16 // this is expected value

标签： java

Answer 1

基本情况应该返回depth而不是累加depthSum。

基本情况是问：

没有子节点的子树的深度和是多少？

它是depth那个子树的！depthSum将包括我们计算过的节点的所有深度，其中一些不在我们询问的子树中，所以是不正确的。

此外，递归情况也应该添加depth到两个子树的总和中。

递归案例是问：

具有两个子子树的子树的深度和是多少？

它是这些子子树的深度和加上子树本身的深度之和！

root.left另请注意，当和中的一个root.right为空时，您忘记了这种情况。

处理完这些情况后，代码如下所示：

public static int nodeDepths(BinaryTree root, int depth, int depthSum) {
    depth = depth + 1;
    depthSum = depthSum + depth;
    sum = sum + depth;

    int retVal = depth;

    if (root.left != null) {
        retVal += nodeDepths(root.left, depth, depthSum);
    }

    if (root.right != null) {
        retVal += nodeDepths(root.right, depth, depthSum);
    }

    return retVal;

}