用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.

干杯，托尼

推荐答案

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屋！