在二叉搜索树中查找高度

Question

我想知道有没有人能帮我改进这个方法来找到二叉搜索树的高度。到目前为止，我的代码看起来像这样。但是，我得到的答案比实际高度大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;
    }
}

- mike

---

我在我的公共方法中返回findHeight(node)-1以正确返回高度。但是我觉得这是不太优秀的代码，你们有什么关于重构的建议吗？ - mike

这是解决树高的正确方法吗？https://github.com/joeyajames/Python/issues/1 - rittam

Answer 1

问题在于你的基本情况。

“树的高度是从根到树中最深节点的路径长度。只有一个节点（根）的（有根）树的高度为零。”- 维基百科 如果没有节点，你想返回-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;
    }
}

- Corey

---

我的公共方法在没有减1的情况下可以正确地工作。但我仍然对这个具有递归的方法如何工作感到困惑。我在if语句后声明了left和right两个整数，但我不明白它们是如何通过这个方法进行递增的。 - mike

这种方法是通过在基本情况下减去1来工作的，它们像其他给定的方法一样递增，当您深入树中时，将高度加1。 - Corey

对于那些对这种递归如何工作感到困惑的人，我制作了一个视频，首先在高层次上解释了该过程，然后我们使用示例运行代码：[查找二叉树的高度]（https://www.youtube.com/watch?v=AWIJwNf0ZQE）。希望你们中的许多人会发现它有用，如果是这样的话，我们应该将它添加到这个答案中。 - cute_ptr

树中节点的高度是从该节点到叶子节点的最长简单向下路径上的边数，而树的高度是其根节点的高度。根据这个定义，由单个（根）节点组成的树的高度为零，这意味着这是唯一正确的答案。该定义来自CLRS（第3版）的第1177页。 - tmakino

@cute_ptr - 这个视频非常有帮助，可以理解这个算法的递归本质。谢谢！！ - N1B4

Answer 2

二叉搜索树的高度等于层数减一。

请参见http://en.wikipedia.org/wiki/Binary_tree上的图表。

你的递归很好，只需在根级别减去1。

还要注意，您可以通过处理空节点来简化函数：

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}

- Stephen

---

我第一次尝试使用类似这样的方法，但是当我运行代码时，总是出现堆栈溢出异常。我猜测是因为我检查了指向null的指针。 - mike

很可能是你的“node == null”没有正确终止。 - Stephen

Stephen，对于单节点树，应该是0吧？但这个返回值是1。 - Matthew Flaschen

@Matthew：你说得对，但我建议他的公共函数从结果中减去一个。相反，你可以通过在基本情况下返回-1来“修复”递归函数。 - Stephen

对于单个节点的树，高度为0。因此对于空树，高度为-1。这就是为什么当节点为空时，“返回-1”有效而不是“返回0”的原因。 - AruniRC

Answer 3

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

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

- Harish

Answer 4

我认为，您的代码可以简化一些。与其尝试在子指针为空时结束递归，不如仅在当前指针为空时结束递归。这样写起来会简单很多。伪代码如下：

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

- Jerry Coffin

---

虽然无法在空对象上调用方法 :) - jemfinch

@jemfinch，在哪里对空对象进行了调用？难道这不是基本情况的处理吗？ - Corey

@jemfinch：我猜我没有建议做这样的事情是件好事！ - Jerry Coffin

为什么你返回0而不是-1？ - johnny 5

@JerryCoffin 我没有在做任何作业。是0还是-1？为什么？ - Faraz

@Faraz：这取决于你认为单节点树的高度是多少。有些人认为高度为0（此时返回-1），而其他人认为高度为1（此时返回0）。 - Jerry Coffin

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

- user17711

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

- lingareddyk

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。这里使用了高度的定义（由Stephen提到）为层数-1。

- Matthew Flaschen

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

往往简化代码比找出它为什么偏差1更容易。这段代码很容易理解：四种可能的情况都得到了明确处理，而且是显然正确的方式：

• 如果左右两棵树都为空，则返回0，因为按定义，单个节点的高度为0。（之前是1）
• 如果左或右树中有一棵为空（但不是两棵！），则返回非空树的高度，再加上1以计算当前节点的增加高度。
• 如果两棵树都不为空，则返回更高子树的高度，再加上1表示当前节点的高度。

- jemfinch

---

这段代码是有效的，而且比我之前写的更清晰，但它仍然返回高度+1。在我的书中，高度被定义为从根到最深叶子节点的路径长度。所以根据我的理解，包含15、25、30、45（按此顺序）的BST只有3个高度，对吗？ - mike

实际上，只有根节点的树高为0而不是1。 - Corey

奇怪。如果他们真正的意思是“下降路径”，那么它真的不应该被称为“高度”，但不幸的是，这似乎是标准术语。正确的修复方法是将第一个情况（node.left == null && node.right == null）更改为返回0。 - jemfinch

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

- Desire

Answer 10

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

从左右子树中取最大高度并加1。这也处理了基本情况（只有一个节点的树的高度为0）。请保留HTML标签。

- Mahendra suthar