Подсчитать количество узлов в двоичном дереве в Java

Question

static int sum=0;
    public static int size(TreeNode root){
        if(root==null)
        return sum;
        sum++;
        sum=size(root.left);
        sum=size(root.right);
        return sum;
    }

Нам нужно просто завершить функцию «размер», которая подсчитывает количество узлов в двоичном дереве.Я написал вышеуказанный код.Это дает неправильный ответ для некоторых тестовых случаев.Пожалуйста, объясните, что не так в приведенном выше коде.

Answer 1

Здесь:

sum=size(root.left);
sum=size(root.right);

Вы вычисляете две суммы, чтобы затем выбросить первую!

Вместо этого вы можете: return size(root.left)+size(root.right) + 1.

Здесь также нет смысла использовать статическое поле sum.Если вообще, это должна быть локальная переменная в этом рекурсивном методе!Соответственно: просто return 0 для нуля, в противном случае используйте возврат, который я предоставил здесь. нет необходимости для этой sum переменной в первую очередь!

Answer 2

Попробуйте что-то вроде этого:

public static int size(final TreeNode node)
{
    if (null == node ) return 0;
    return 1 + size( node.left ) + size( node.right );
}

Answer 3

Вы неправильно установили sum при получении данных от дочернего узла

    sum += size(root.left);
    sum += size(root.right);

Я бы посоветовал вам не использовать глобальную статическую переменную для получения значения, когда вы хотите сделать это рекурсивно

    static int sum=0;
    public static int size(TreeNode root){
        if(root==null)
        return 0;
        int cnt = 0;
        cnt++;
        cnt += size(root.left);
        cnt += size(root.right);
        return cnt;
    }