java - 计算树中节点的方法

Question

如果您的方法参数是根节点，我了解如何计算二叉搜索树中的节点，我只是想知道如果方法调用参数是除根之外的节点，是否有办法计算它们？

我原来有:

public int size(BSTNode cur)
{
    if (cur == null)
        return 0;
    return 1 + size(cur.getLeft()) + size(cur.getRight());  
}

只有当我在方法调用中使用的节点是根时，这才有效，否则它只返回子树中的节点数，而不是整个树。

Answer 1

如果您的树节点有到父级的链接，您可以一直向上到根(即没有父级的节点):

TreeNode node = ...
while (node.parent != null) {
    node = node.parent; // Go up the tree
}
// Now you are at the root, so you can count all nodes

否则，该任务是不可能的，因为无法到达树中更高的其他节点。