Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

Input: root = [1,2]
Output: 1

👨‍💻 Алгоритм:

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

class Solution {
    constructor() {
        this.diameter = 0;
    }
    
    diameterOfBinaryTree(root) {
        this.diameter = 0;
        this.longestPath(root);
        return this.diameter;
    }
    
    longestPath(node) {
        if (node === null) return 0;
        
        let leftPath = this.longestPath(node.left);
        let rightPath = this.longestPath(node.right);
        
        this.diameter = Math.max(this.diameter, leftPath + rightPath);
        
        return Math.max(leftPath, rightPath) + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний