java - 通过递归查找 BST 的大小

Question

尝试在链接的 BST 中递归查找大小（总对象）。得到奇怪的错误回报，不完全确定为什么。

 private int size(BinaryTreeNode<T> root)
   {
      if (root == null) // empty tree
         return 0;
      
      if (root.getRight() == null && root.getLeft() == null) // base case, only root node exists
         return 1;
         
      else if (root.getRight() == null && root.getLeft() != null) // only left node exists
         return size(root.getLeft()) + 1;
      else if (root.getRight() != null && root.getLeft() == null) // only right node exists
         return size(root.getRight()) + 1;
      else
         return size(root.getRight()) + size(root.getLeft()) + 1; // right and left nodes exist
   }

查找树的大小时：

    < 33 >
 1 >     < 67 >
   12 >  1    80
      13

我得到 1 作为返回大小而不是 6。

标签： javadata-structuresbinary-treebinary-search-tree

Answer 1

您的代码看起来正确，但可以简化为。

    private int size(BinaryTreeNode<T> root)
    {
        if (root == null) // empty tree
            return 0;
        
        return 1 + size(root.getLeft()) + size(root.getRight());

    }