在二叉搜索树中查找高度

Question

我想知道是否有人可以帮助我重新设计这个方法来找到二叉搜索树的高度。到目前为止，我的代码如下所示。然而，我得到的答案比实际高度大 1。但是当我从 return 语句中删除 +1 时，它比实际高度小 1。我仍然试图用递归来解决我的问题这些二叉搜索树。任何帮助将不胜感激。

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;
    }
}

Answer 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;
    }
}

Answer 2

二叉搜索树的高度等于层数 - 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));
}

Answer 3

int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Answer 4

在我看来，稍微简化一下您的代码将会受益。当 child 指针为 null 时，不要尝试结束递归，而是仅在 current 指针为 null 时结束递归无效的。这使得代码编写起来更加简单。在伪代码中，它看起来像这样：

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

Answer 5

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;
    }

Answer 6

对于像我这样喜欢单线解决方案的人：

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}

Answer 7

这是一个简洁且希望正确的表达方式：

  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;
  }

如果当前节点为空，则不存在树。如果两个孩子都是，则只有一个层，这意味着高度为 0。这使用高度的定义（由斯蒂芬提到）作为层数 - 1

Answer 8

这未经测试，但显然是正确的：

private int findHeight(Treenode<T> 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));
  }
}

通常简化代码比弄清楚为什么它会差一更容易。这段代码很容易理解：四种可能的情况都以明显正确的方式清楚地处理：

• 如果左树和右树都为空，则返回 0，因为根据定义单个节点的高度为 0。（为 1）
• 如果左树或右树（但不是两者！）都为空，返回非空树的高度，加上 1 以说明当前节点的添加高度。
• 如果两棵树都不为空，则返回较高子树的高度，并为当前节点再次加一。

Answer 9

    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() 中打印它。

Answer 10

上面给出的高度定义是不正确的。这就是深度的定义。

“树中节点M的深度是从树根到M的路径长度。树的高度比深度大一树中最深节点的所有深度为 d 的节点都位于树中的 d 层，根是唯一位于 0 层的节点，其深度为 0。 ”。

引文：“数据结构和算法分析实用介绍”
3.2版（Java版）
克利福德·谢弗
计算机科学系
弗吉尼亚理工大学
布莱克斯堡, VA 24061

Answer 11

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;
}

Answer 12

//求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;
}

Answer 13

int height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

取左右子树的最大高度并加 1。这也处理基本情况（具有 1 个节点的树的高度为 0）。

Answer 14

我知道我参加聚会迟到了。在研究了这里提供的精彩答案之后，我认为我的答案将为这篇文章增加一些价值。尽管发布的答案令人惊叹且易于理解，但它们都是在线性时间内计算 BST 的高度。我认为这可以改进，并且可以在恒定时间内检索高度，因此写下这个答案 - 希望你会喜欢它。
让我们从 Node 类开始：

public class Node
{
    public Node(string key)
    {
        Key = key;
        Height = 1;
    }    

    public int Height { get; set; } 
    public string Key { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public override string ToString()
    {
        return $"{Key}";
    }
}

BinarySearchTree 类

所以您可能已经猜到了这里的技巧...我保留节点实例变量 Height 来跟踪添加的每个节点。
让我们转到 BinarySearchTree 类，它允许我们将节点添加到 BST 中：

public class BinarySearchTree
{
    public Node RootNode { get; private set; }

    public void Put(string key)
    {
        if (ContainsKey(key))
        {
            return;
        }

        RootNode = Put(RootNode, key);
    }

    private Node Put(Node node, string key)
    {
        if (node == null) return new Node(key);

        if (node.Key.CompareTo(key) < 0)
        {
            node.Right = Put(node.Right, key);
        }
        else
        {
            node.Left = Put(node.Left, key);
        }       
        
        // since each node has height property that is maintained through this Put method that creates the binary search tree.
        // calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it.        
        node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
        return node;
    }

    private int GetHeight(Node node)
    {
        return node?.Height ?? 0;
    }

    public Node Get(Node node, string key)
    {
        if (node == null) return null;
        if (node.Key == key) return node;

        if (node.Key.CompareTo(key) < 0)
        {
            // node.Key = M, key = P which results in -1
            return Get(node.Right, key);
        }

        return Get(node.Left, key);
    }

    public bool ContainsKey(string key)
    {
        Node node = Get(RootNode, key);
        return node != null;
    }
}

一旦我们在 BST 中添加了键、值，我们就可以调用 RootNode 对象的 Height 属性，该属性将返回 < 中 RootNode 树的高度强>恒定时间。
诀窍是在将新节点添加到树中时保持高度更新。
希望这对计算机科学爱好者的狂野世界有所帮助！

单元测试：

[TestCase("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 8)]
public void HeightTest(string data, int expectedHeight)
{
    // Arrange.
    var runner = GetRootNode(data);

    
    //  Assert.
    Assert.AreEqual(expectedHeight, runner.RootNode.Height);
}

private BinarySearchTree GetRootNode(string data)
{
    var runner = new BinarySearchTree();
    foreach (char nextKey in data)
    {
        runner.Put(nextKey.ToString());
    }

    return runner;
}

注意：在每次 Put 操作中保持树的高度的想法受到《Size of BST》第 3 章（第 399 页）中的方法的启发。 算法（第四版）一本书。

Answer 15

我想这个问题可能意味着两个不同的事情......

1. 高度是最长分支中的节点数：-

   int calcHeight(节点*根){
如果（根==NULL）
返回0；
int l=calcHeight(root->left);
int r=calcHeight(根->右);
如果(l>r)
返回l+1；
别的
返回r+1；
}


2. 高度是树本身节点总数：

   int calcSize(节点*根){
如果（根==NULL）
返回0；
return(calcSize(根->左)+1+calcSize(根->右));
}

Answer 16

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;
}

Answer 17

将 tempHeight 设置为静态变量（初始为 0）。

静态无效findHeight（节点节点，int计数）{

    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);

}

Answer 18

这是 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);
    }

Answer 19

 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }

Answer 20

这是 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);
    }

Answer 21

二叉树的高度

public static int height(Node root)
    {
        // Base case: empty tree has height 0
        if (root == null) {
            return 0;
        }

        // recursively for left and right subtree and consider maximum depth
        return 1 + Math.max(height(root.left), height(root.right));
    }

Answer 22

对于其他读到此内容的人！！！！

HEIGHT 定义为从根节点到叶节点的最长路径中的节点数。因此：只有根节点的树的高度为 1 而不是 0。

给定节点的 LEVEL 是距根的距离加 1。因此：根位于第 1 层，其子节点位于第 2 层，并且很快。

（信息由《数据结构：使用 Java 进行抽象和设计》第二版提供，作者：Elliot B. Koffman 和 Paul AT Wolfgang）- 我目前在哥伦布州立大学学习的数据结构课程中使用的书籍。

Answer 23

在此处输入图像描述

根据 Thomas H. Cormen、Charles E. 的“算法简介” Leiserson、Ronald L. Rivest 和 Clifford Stein 给出了树高的定义：

a中节点的高度
树是从节点到节点的最长简单向下路径上的边数
一片叶子，一棵树的高度就是它的根的高度。树的高度也是
等于树中任何节点的最大深度。

以下是我的红宝石解决方案。大多数人在实现中忘记了空树或单节点树的高度。

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

Answer 24

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));
}

Answer 25

我自己也在努力解决这个问题，试图找到一些优雅的东西，但仍然能产生正确的值。这是我使用 Swift 的想法。请注意，height 是一个计算变量，从技术上讲不是一个函数。

class Node<T: Comparable>: NSObject
{
    var left: Node<T>? = nil
    var right: Node<T>? = nil
 
    var isLeaf: Bool { left == nil && right == nil }

    var height: Int {
        if isLeaf { return 0 }
        return 1 + max(left?.height ?? 0, right?.height ?? 0)
    }
}

这个 Node 定义还有更多内容，但您可以看到 left 和 right 变量（可能为零）以及 isLeaf var true 当 left 和 right 均为 nil 时。可能不是最有效的，但我相信它会产生正确的结果。

BST 定义还有一个计算的高度变量，当树为空时返回 -1。

class BST<T: Comparable>: NSObject
{
    var root: Node<T>?
    var height: Int { root != nil ? root!.height : -1 }
}

Answer 26

HackerRank Day 22: Finding height in Binary Search Tree, in C#.

     static int getHeight(Node root)
        {
            //Write your code here
            int countr = 0,countl=0;
            Node Leftsubtree=root.left;
            Node rightsubtree = root.right;
            int data=root.data;
             if(root==null ||(root.left == null && root.right == null))
            {
                return 0;
            }
             else
            {
                while (Leftsubtree != null)
                {
                        if(Leftsubtree.data<data)
                        {
                        Leftsubtree = Leftsubtree.left==null?Leftsubtree.right:Leftsubtree.left;
                        countl++;
                        }
                }
                while (rightsubtree != null)
                {
                    if (rightsubtree.data > data)
                    {
                        rightsubtree = rightsubtree.right == null ? rightsubtree.left : rightsubtree.right;
                        countr++;
                    }
    
                }
            }
    
            return countr >= countl ? countr : countl;
    
    
        }