计算树中的两个版本离开树

Question

这两个版本之间有什么区别？

public static int countLeaves(IntTreeNode root) { 
    if (root == null) { 
     return 0; 
    } else 
     return 1 + countLeaves(root.left) + countLeaves(root.right); 
} 

public static int countLeaves(IntTreeNode root) { 
    if (root == null) { 
     return 0; 
    } else if (root.left == null && root.right == null) { 
     return 1; 
    } else 
     return countLeaves(root.left) + countLeaves(root.right); 
} 

我在互联网上找不到任何使用第一个版本的东西。 第一个版本是否错误？

我试图在纸上描绘它们，它们看起来是一样的。 但我只想确定一下。

Answer 1

第一个似乎计算树中的所有节点，而第二个计算所有叶节点。

的确，在第一个中，当没有有效的树时，递归停止（root == null），并且它总是进入递归检查左右树的1（对于当前节点）。

第二个只使用条件if (root.left == null && root.right == null)来计数叶子。

这是假设叶被识别为具有nullroot.left和nullroot.right的节点。

Answer 2

第一个版本不算叶 - 它是计数节点。

第二个版本的确在计算叶子。

这些方法将不返回相同的结果，在这里是一个例子：

root(5) 
    / \ 
leaf(3) leaf(7) 

用于这种树中的第一种方法将返回图3（节点的数量），第二个将返回2（数叶子）。