困惑-二叉树的高度 [英] Confused - Height of Binary tree

问题描述

我对计算二叉树高度的逻辑有些困惑.

I'm somewhat confused between the logic of calculating the height of binary tree.

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

}

代码2

public static int findHeight(Tree node) {
    if(node == null)
        return -1;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

我认为，第二个是正确的，因为它为以下代码提供了正确的答案:-

I think, the second one is correct, since it gives the correct answer for below code :-

Tree t4 = new Tree(4);
Tree t2 = new Tree(2);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
Tree t5 = new Tree(5);

t4.left = t2;
t4.right = t5;

t2.left = t1;
t2.right = t3;

// Prints "Height : 2" for Code 2
// Prints "Height : 3" for Code 1
System.out.println("Height : " + findHeight(t4)); 

我很困惑，因为许多其他的答案都显示了根据代码1计算高度的逻辑

I'm confused because many of other SO answers shows the logic for calculating height as per Code 1

矛盾逻辑

• 在二进制搜索树中查找高度
• 二叉树的高度

更新:

所有，我对树的高度到底有什么基本怀疑?

All, I've a basic doubt as to what is exactly the height of tree ?

1.是树的根节点和最深节点(包括根和最深节点)之间的节点数吗?

2.是树的根节点与最深节点之间的边数吗?

或

3.仅仅是每个人的实施问题-两种方法都是正确的吗?

推荐答案

不同之处在于，如果一棵空树的高度为-1或0.

The difference all lies in if an empty tree has height -1 or 0.

根据维基百科:

节点的高度是从该节点到叶子的最长的向下路径的长度.根的高度是树的高度.节点的深度是指其根路径(即其根路径)的长度.

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).

和

根节点的深度为零，叶节点的高度为零，只有一个节点的树(因此根和叶)的深度和高度为零.通常，一棵空树(如果允许，则没有节点的树)的深度和高度为-1.

The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.

所以您可能是对的-第二个人对此表示同意.

So you might be right - the second one agrees about this.

当然，这些全都是定义-看到与第一个版本一致的定义我不会感到惊讶.

Of course, these are all definitions - I would not be too amazed to see a definition that agrees with the first version.

这篇关于困惑-二叉树的高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！