我想知道是否有人可以帮我修改这个方法来找到二叉搜索树的高度。到目前为止，我的代码看起来像这样。但是，我得到的答案比实际高度大1.然而当我从我的返回语句中删除+1时，它比实际高度小1.我仍然试图用我的头围绕递归这些BST。任何帮助将非常感激。
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
问题出在你的基础案例中。
“树的高度是树中从根到最深节点的路径长度。只有一个节点（根）的（根）树的高度为零。” - Wikipedia
如果没有节点，则要返回-1而不是0.这是因为最后添加1。
因此，如果没有节点，则返回-1，取消+1。
int findHeight(TreeNode<T> aNode) {
if (aNode == null) {
return -1;
}
int lefth = findHeight(aNode.left);
int righth = findHeight(aNode.right);
if (lefth > righth) {
return lefth + 1;
} else {
return righth + 1;
}
}
上面给出的高度定义是不正确的。这就是深度的定义。
“树中节点M的深度是从树的根到M的路径的长度。树的高度比树中最深节点的深度多一个。深度为d的所有节点都是在树中的d级。根是0级唯一的节点，其深度为0。
引用：“数据结构和算法分析的实用介绍”3.2版（Java版）Clifford A. Shaffer计算机科学系弗吉尼亚理工大学布莱克斯堡，VA 24061
public int height(){
if(this.root== null) return 0;
int leftDepth = nodeDepth(this.root.left, 1);
int rightDepth = nodeDepth(this.root.right, 1);
int height = leftDepth > rightDepth? leftDepth: rightDepth;
return height;
}
private int nodeDepth(Node node, int startValue){
int nodeDepth = 0;
if(node.left == null && node.right == null) return startValue;
else{
startValue++;
if(node.left!= null){
nodeDepth = nodeDepth(node.left, startValue);
}
if(node.right!= null){
nodeDepth = nodeDepth(node.right, startValue);
}
}
return nodeDepth;
}
int height(Node* root) {
if(root==NULL) return -1;
return max(height(root->left),height(root->right))+1;
}
从左右子树获取最大高度并将其加1。这也处理基本情况（具有1个节点的树的高度为0）。
我想这个问题可能意味着两件事......
int calcHeight(node* root){
if(root==NULL)
return 0;
int l=calcHeight(root->left);
int r=calcHeight(root->right);
if(l>r)
return l+1;
else
return r+1;
}
int calcSize(node* root){
if(root==NULL)
return 0;
return(calcSize(root->left)+1+calcSize(root->right));
}public int getHeight(Node node)
{
if(node == null)
return 0;
int left_val = getHeight(node.left);
int right_val = getHeight(node.right);
if(left_val > right_val)
return left_val+1;
else
return right_val+1;
}
将tempHeight设置为静态变量（最初为0）。
static void findHeight（Node node，int count）{
if (node == null) {
return;
}
if ((node.right == null) && (node.left == null)) {
if (tempHeight < count) {
tempHeight = count;
}
}
findHeight(node.left, ++count);
count--; //reduce the height while traversing to a different branch
findHeight(node.right, ++count);
}
这是Java中的一个解决方案有点冗长，但有效..
public static int getHeight (Node root){
int lheight = 0, rheight = 0;
if(root==null) {
return 0;
}
else {
if(root.left != null) {
lheight = 1 + getHeight(root.left);
System.out.println("lheight" + " " + lheight);
}
if (root.right != null) {
rheight = 1+ getHeight(root.right);
System.out.println("rheight" + " " + rheight);
}
if(root != null && root.left == null && root.right == null) {
lheight += 1;
rheight += 1;
}
}
return Math.max(lheight, rheight);
}
int getHeight(Node* root)
{
if(root == NULL) return -1;
else return max(getHeight(root->left), getHeight(root->right)) + 1;
}
//用于查找BST高度的函数
int height(Node* root) {
if(root == NULL){
return -1;
}
int sum=0;
int rheight = height(root->right);
int lheight = height(root->left);
if(lheight>rheight){
sum = lheight +1;
}
if(rheight > lheight){
sum = rheight + 1;
}
return sum;
}
这是C＃的解决方案
private static int heightOfTree(Node root)
{
if (root == null)
{
return 0;
}
int left = 1 + heightOfTree(root.left);
int right = 1 + heightOfTree(root.right);
return Math.Max(left, right);
}
二叉搜索树的高度等于number of layers - 1。
请参阅http://en.wikipedia.org/wiki/Binary_tree上的图表
你的递归是好的，所以只需在根级别减去一次。
另请注意，您可以通过处理空节点来清理函数：
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}
对于其他读这个的人！
HEIGHT定义为从根节点到叶节点的最长路径中的节点数。因此：只有根节点的树的高度为1而不是0。
给定节点的LEVEL是距离根加1的距离。因此：根位于1级，其子节点位于2级，依此类推。
（信息由Data Structures：Abstraction and Design Using Java提供，第2版，作者：Elliot B. Koffman和Paul A. T. Wolfgang） - 用于数据结构课程的书我目前正在哥伦布州立大学学习。
根据Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest和Clifford Stein的“算法导论”，以下是树高的定义：
树中节点的高度是从节点到叶子的最长简单向下路径上的边数，树的高度是其根的高度。树的高度也等于树中任何节点的最大深度。
以下是我的红宝石解决方案。大多数人在实现时忘记了空树的高度或单个节点的树。
def height(node, current_height)
return current_height if node.nil? || (node.left.nil? && node.right.nil?)
return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
return height(node.left, current_height + 1) if node.left
return height(node.right, current_height + 1)
end
int maxDepth(BinaryTreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
int getHeight(Node node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
IMO，您的代码将受益于简化一点。当子指针为null时，不要尝试结束递归，而只在当前指针为空时结束它。这使得编写代码变得更加简单。在伪代码中，它看起来像这样：
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
这是未经测试的，但相当明显正确：
private int findHeight(Treenode aNode) {
if (aNode.left == null && aNode.right == null) {
return 0; // was 1; apparently a node with no children has a height of 0.
} else if (aNode.left == null) {
return 1 + findHeight(aNode.right);
} else if (aNode.right == null) {
return 1 + findHeight(aNode.left);
} else {
return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
}
}
通常简化代码比找出它的原因更容易。这段代码很容易理解：四种可能的情况以明显正确的方式清楚地处理：
class Solution{
public static int getHeight(Node root) {
int height = -1;
if (root == null) {
return height;
} else {
height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
return height;
}
像我这样喜欢一线解决方案的人：
public int getHeight(Node root) {
return Math.max(root.left != null ? getHeight(root.left) : -1,
root.right != null ? getHeight(root.right) : -1)
+ 1;
}
这是一个简洁而有希望的正确表达方式：
private int findHeight(TreeNode<T> aNode){
if(aNode == null || (aNode.left == null && aNode.right == null))
return 0;
return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
}
如果当前节点为null，则没有树。如果两个孩子都是，那么就有一层，这意味着0高。这使用高度的定义（由Stephen提到）作为层数＃1
public void HeightRecursive()
{
Console.WriteLine( HeightHelper(root) );
}
private int HeightHelper(TreeNode node)
{
if (node == null)
{
return -1;
}
else
{
return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));
}
}
C＃代码。在BST类中包含这两种方法。你需要两种方法来计算树的高度。 HeightHelper计算它，＆HeightRecursive在main（）中打印它。