java - 如何计算二叉树中 "only child"节点的数量？

Question

注意:这是与作业相关的，但我不会这样标记它，因为“作业”标签被标记为已过时(？)

使用以下实现二叉树的类...

class TreeNode
{
  private Object value; 
  private TreeNode left, right;

   public TreeNode(Object initValue)
  { 
     value = initValue; 
     left = null; 
     right = null; 
  }

   public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
  { 
     value = initValue; 
     left = initLeft; 
     right = initRight; 
  }

   public Object getValue()
  { 
     return value; 
  }

   public TreeNode getLeft() 
  { 
     return left; 
  }

   public TreeNode getRight() 
  { 
     return right; 
  }

   public void setValue(Object theNewValue) 
  { 
     value = theNewValue; 
  }

   public void setLeft(TreeNode theNewLeft) 
  { 
     left = theNewLeft;
  }

   public void setRight(TreeNode theNewRight)
  { 
     right = theNewRight;
  }

}

我需要计算二叉树中“独生子”节点的数量，这被定义为不具有源自其父节点的另一个节点的节点。

这是我到目前为止所拥有的:

public static int countOnlys(TreeNode t)
  {
     if(t == null)
         return 0;
     if(isAnOnlyChild(t))
         return 1;
     return countOnlys(t.getLeft()) + countOnlys(t.getRight());
  }

我不知道如何实现boolean方法isAnOnlyChild(TreeNode t)

有人可以帮我吗？

Answer 1

您已经非常接近并且遍历看起来不错，但是在您的 Treenode 中，您的子节点与其父节点之间没有链接。因此，您无法从左 child 中判断是否存在 sibling (右 child )。

您可以有一个父 Treenode(以及左节点和右节点)，这样您就可以检查给定节点的父节点有多少个子节点。或者如 ajp15243 建议的那样，使用一种方法来检查给定节点有多少个子节点。

后者的一些伪代码:

//we still need to check if that only child has its own children
if hasOnlyChild(t) 
      return 1 + checkOnlys(left) + checkOnlys(right)
else 
      return checkOnlys(left) + checkOnlys(right)