为什么递归导致计数为 return 2 而不是 4？

Question

我正在尝试在 Leetcode 上做平衡树问题，你 return 只有当左子树的高度 - 右子树的高度 <= 1 时才为真。为什么左子树的深度 return 是 2 而它应该 return 4？有什么我解释错了吗？我在底部附上了一张树的照片。

输入：[1,2,2,3,3,null,null,4,4,null,null,5,5]

输出：真（因为左子树是 returning 2 而不是 4）

预期输出：假

打印报表：

左子树：2

右子树：1

结果：1（左子树 - 右子树）

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
    // 1 2 2 3 3 4 4
    // 
      
    if (root == null) return true;
    System.out.println("left subtree: " + findDepth(root.left,1));   
    System.out.println("right subtree: " + findDepth(root.right,1));   
    System.out.println("result: " + Math.abs(findDepth(root.left,1) - findDepth(root.right, 1)));
    if ( Math.abs(findDepth(root.left,1) - findDepth(root.right, 1)) <= 1) return true;
    return false;
    }
  
  public static int findDepth(TreeNode root, int count) {
    if (root == null) return count;
    if (root.left != null) {
       count++;
       findDepth(root.left, count);
    }
     if(root.left == null && root.right == null) return count;

    return count;
  }
    
}

Image of Binary Tree

Answer 1

因为您只是通过应用条件

计算findDepth方法中树左侧的深度

if (root.left != null) {
   count++;
   findDepth(root.left, count);
}

你可以这样修改你的方法

  public static int findDepth(TreeNode root, int count) {
    if (root == null) return count;
   
    return Math.max(findDepth(root.left, count+1),findDepth(root.right, count+1));
  }

Answer 2

你得到 2 的原因是因为当你递归时，递归调用不会增加你传入的 count 变量。相反，它会增加它自己的 copy 它的。 Java is pass by value.

if (root.left != null) {
   count++;
   // the call below will not change "count" at all
   findDepth(root.left, count);
   // it will only change its own copy
}

因此，递归调用实际上什么都不做。您甚至没有使用它的 return 值。它的 return 值实际上是 count 的修改副本，您希望将 count 设置为，因此要解决此问题，请将 count 设置为 return 值共 findDepth：

value = findDepth(root.left, count);

这会给你预期的 4，但你的 findDepth 也应该检查正确的子树，并且可以通过其他方式改进。例如，您实际上不需要 count 参数。

public static int findDepth(TreeNode root) {
    if (root == null) return 0;
   
    return 1 + Math.max(findDepth(root.left), findDepth(root.right));
}

为什么递归导致计数为 return 2 而不是 4？

Why is recursion causing the count to return 2 instead of 4?

java

binary-tree