Диаметр бинарного дерева от 1

Question

Я новичок в области рекурсии и деревьев. У меня проблемы с определением диаметра бинарного дерева. Мое решение отключено на 1, и я не могу понять, где я иду не так. Я рассмотрел похожий вопрос здесь: Нахождение диаметра дерева , но я не могу понять, действительно ли это та же проблема. Ответ на рисунок ниже имеет диаметр 8 (самый длинный путь между двумя узлами). Однако я получаю 7. Любая помощь или совет приветствуется. Заранее спасибо.

С вопросами можно ознакомиться здесь: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3293/

Я провалил только 4 из 106 тестовых случаев.

public class DiameterBinaryTree {

    public static void main(String argv[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(diameter(root));
    }

    public static int diameter(TreeNode root){
        int maxDiameter = Integer.MIN_VALUE;
        return diameterHelper(root, maxDiameter) ;
    }

    public static int diameterHelper(TreeNode root, int maxDiameter){
        if(root == null ) return 0;
        diameterHelper(root.left, maxDiameter);
        int leftHeight = findHeight(root.left);
        diameterHelper(root.right, maxDiameter);
        int rightHeight = findHeight(root.right);
        return Math.max(maxDiameter, leftHeight + rightHeight) ;
    }

    public static int findHeight(TreeNode root ){
        int countLeft = Integer.MIN_VALUE;
        int countRight = Integer.MIN_VALUE;
        return findHeightHelper(root, countLeft, countRight) ;
    }

    public static int findHeightHelper(TreeNode root, int countLeft, int countRight){
        if(root == null ) return 0;
        countLeft = 1 + findHeightHelper(root.left, countLeft, countRight);
        countRight = 1 + findHeightHelper(root.right, countLeft, countRight);
        return Math.max(countLeft, countRight) ;
    }
}

Answer 1

Я не учел максимальный диаметр слева и максимальный диаметр справа, прежде чем сравнивать текущий диаметр.

return Math.max (Math.max (leftDiameter, rightDiameter), leftHeight + rightHeight) ;

Answer 2

расстояние между -4 (дочерний элемент 6) и -2 (дочерний элемент 9) равен 8. Но для поиска диметрового дерева мы можем запустить поиск bfs с одного узла (любого узла), а затем снова запустить bfs с самого длинного узла, который мы находим в первых bfs, а наибольшее расстояние - это наше дерево диаметров. и порядок этого алгоритма o (n + m). Надеюсь, это поможет