计算 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;
    }

我们只需要完成计算二叉树节点数的函数"size"。我已经写了上面的代码。它对某些测试用例给出了错误的答案。请解释上面的代码有什么问题。

Answer 1

从子节点获取数据时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;
    }

Answer 2

这里：

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

您正在计算两个个总和，然后丢弃第一个！

您可以改为：return size(root.left)+size(root.right) + 1。

这里也没有必要使用静态字段 sum。如果有的话，那应该是该递归方法中的 local 变量！分别：简单地 return 0 为 null，否则使用我在此处提供的 return。首先 不需要 那个 sum 变量！

Answer 3

尝试这样的事情：

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

计算 Java 中二叉树中的节点数

Count number of nodes in binary tree in Java

java

recursion

binary-tree