困惑 - 二叉树的高度

Question

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

代码1

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

}

我认为,第二个是正确的,因为它给出了以下代码的正确答案: -

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

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

矛盾的逻辑

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

---

更新:

总而言之,我对树的高度到底有什么基本的疑问？

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

2.树根和最深节点之间的边缘是否是？

要么

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

Answer 1

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

根据维基百科:

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

和

根节点深度为零,叶节点具有高度为零,并仅具有单个节点树(因此两者根和叶)具有深度和高度为零.通常,空树(没有节点的树,如果允许的话)具有深度和高度-1.

所以你可能是对的 - 第二个人同意这一点.

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