在Java中计算树中的节点 [英] Counting nodes in a tree in Java

问题描述

首先，我发誓这不是家庭作业，这是我在接受采访时被问到的一个问题。我想我弄得一团糟（尽管我确实意识到解决方案需要递归）。这是一个问题：

First of all, I swear this is not homework, it's a question I was asked in an interview. I think I made a mess of it (though I did realise the solution requires recursion). Here is the question:

实现count（）方法，该方法返回树中的节点数。如果节点没有左子节点或右子节点，则相关的 getXXChild（）方法将返回 null

Implement the count() method which returns the number of nodes in a tree. If a node doesn't have either a left or right child, the relevant getXXChild() method will return null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

我提出问题的理由只是很好奇看到正确的解决方案，从而衡量我的糟糕程度。

My reason for asking the question is simply curious to see the correct solution, and thereby measure how bad mine was.

干杯，
Tony

Cheers, Tony

推荐答案

int count() {
  Tree right = getRightChild();
  Tree left = getLeftChild();
  int c = 1;                                      // count yourself!
  if ( right != null ) c += right.count();        // count sub trees
  if ( left != null ) c += left.count();          // ..
  return c;
}

这篇关于在Java中计算树中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！