Confused - Высота двоичного дерева

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

Я confus ред, потому что многие из других SO ответов показывает логику для вычисления высоты в соответствии с Кодексом 1

Противоречивые логик

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

---

UPDATE:

All , У меня есть основное сомнение относительно того, что точно высотой дерева?

1. Не является ли это узлом между корнем и самым глубоким узлом дерева (включая оба - корень & самый глубокий узел)?

2. Разве это не ребро между корнем и самым глубоким узлом дерева?

ИЛИ

3. Является ли это просто вопрос реализации каждого человека - Оба подхода являются правильными?

Answer 1

разница все лежит, если пустое дерево имеет высоту -1 или 0.

Согласно Wikipedia :

Высота узла - это длина самого длинного нисходящего пути к листу от этого узла. Высота корня - высота дерева. Глубина узла - это длина пути к его корню (т. Е. Его корневой путь).

и

корневой узел имеет глубину ноль, листовые узлы имеют нулевую высоту, и дерево только с одним узлом (отсюда и корень и лист) имеет глубину и высоту нулевой. Обычно пустое дерево (дерево без узлов, если таковые разрешены) имеет глубину и высоту -1.

Таким образом, вы можете быть правы - второй согласен с этим.

Конечно, все эти определения - я не был бы слишком удивлен, увидев определение, согласующееся с первой версией.

Answer 2

Ваш пример высоты 3 (t4 - корень, t4.left - t2, t2.left is t1), если ваше понимание высоты (1 корневой узел имеет высоту 1, корневой узел с дочерним или два имеет высоту 2, и т.д.)

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

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

Так код 1 является правильным :))

Answer 3

Код 0 будет считать корень высотой 1 (корень должен быть 0). Это означает, что все последующие деревья будут слишком большим.