Диаметр бинарного дерева рекурсивно с использованием высоты дерева?

Question

Я хочу рассчитать диаметр бинарного дерева, для которого я создал функцию getDiameter(). Теперь в этой функции мне нужно вызвать функцию findHeight() двоичного дерева, которая возвращает высоту двоичного дерева. 2 функции для вычисления высоты в code1 и code2 немного отличаются с точки зрения концепции. В коде1 я рассматриваю высоту дерева с единственным узлом (только с корнем) - 1, а в коде2 я рассматриваю высоту дерева с единственным узлом - 0. Поэтому в базовом случае кода1 я вернул 0 и в code2 Я вернул -1. Я смущен, какой код правильно использовать code1 или Кодекса2, потому что ответ диаметра будет меняться ....

public static int getDiameter(BinaryTreeNode root) {   
    if (root == null) 
     return 0; 

    int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 1; 
    int leftDiameter = getDiameter(root.getLeft()); 
    int rightDiameter = getDiameter(root.getRight()); 

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); 
} 


code1 

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

} 
Code 2 

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

} 

Answer 1

Оба понятия в коде 1 и код 2 правильно найти высоту двоичное дерево.

Дело в том, что вы должны соответствовать функции getDiameter() для двух разных кодов.

Таким образом, если код 1 используется функция getDiameter() будет:

public static int getDiameter(BinaryTreeNode root) {   

if (root == null) 
    return 0; 

int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 1; 
int leftDiameter = getDiameter(root.getLeft()); 
int rightDiameter = getDiameter(root.getRight()); 

return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); 

} 

и если код 2 используется функция getDiameter() будет:

public static int getDiameter(BinaryTreeNode root) {   
if (root == null) 
    return 0; 

int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 3; 
int leftDiameter = getDiameter(root.getLeft()); 
int rightDiameter = getDiameter(root.getRight()); 

return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); 

} 

Теперь ответ диаметра в обоих дела будут правильными .....