混淆 - 二叉树高度

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

我很混淆ED，因为许多其他SO答案的显示逻辑，用于计算高度按码1

矛盾逻辑

• Finding height in Binary Search Tree
• Height of a binary tree

---

UPDATE：

所有，我对于确切的东西有一个基本的疑问树的高度？

1.它是否是树的根节点和最深节点之间的节点（包括两个 - 根&最深的节点）？

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

OR

3，它是实现每个人的只是事情 - 这两种方法是正确的？

Answer 1

的区别在于所有的中，如果一个空树有高度-1或0

据Wikipedia ：

节点的高度是从该节点到叶的最长向下路径的长度。根的高度是树的高度。节点的深度是到其根的路径（即其根路径）的长度。

和

根节点具有深度为零，叶节点具有高度为零，并仅具有单个节点（因此两者根和叶）一个树具有深度和高度为零。通常，空树（没有节点的树，如果允许的话）具有深度和高度-1。

所以你可能是对的 - 第二个人对此表示赞同。

当然，这些都是定义 - 我不会很惊讶地看到一个定义与第一个版本一致。

Answer 2

你的例子是高度3的（T4是根，t4.left为t2，t2.left为t1）如果您的高度的理解是（1个节点是高度1的，具有子根节点或二是身高2等）

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

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

所以代码1是正确的:)）

Answer 3

代码0将根作为高度1（根应该为0）。这意味着所有后续的树木将是一个太多