混淆 - 二叉樹高度

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）。這意味着所有後續的樹木將是一個太多