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

disbfnqx 于 2021-08-20 发布在 Java

关注(0)|答案(2)|浏览(319)

我试图在leetcode上做平衡树问题，只有当左子树的高度-右子树的高度<=1时，才返回true。为什么左子树的深度返回2，而它应该返回4？有什么我解释错了吗？我在底部贴了一张树的照片。
输入：[1,2,2,3,3，空，空，4,4，空，空，5,5]
输出：true（因为左子树返回的是2而不是4）
预期输出：false
打印报表：
左子树：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;
  }

}

二叉树图像

Java binary-tree

来源：https://stackoverflow.com/questions/68325024/why-is-recursion-causing-the-count-to-return-2-instead-of-4

2条答案

按热度按时间

9lowa7mx1#

得到2的原因是，当您递归时，递归调用不会增加 count 您传入的变量。相反，它会增加自己的副本。java是按值传递的。

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
}

因此，递归调用实际上什么都不做。您甚至没有使用它的返回值。它的返回值实际上是 count 你想要的 count 要设置为，所以要解决此问题，请设置 count 到的返回值 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));
}

赞(0）回复(0）举报 2021-08-20

46qrfjad2#

因为你只是在计算树左边的深度 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));
  }

赞(0）回复(0）举报 2021-08-20

我来回答

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

2条答案

相关问题

热门标签

最新问答