✅ Решение задачи 1373

Time: O(n)
Space: O(n)

💡 Идея
🟦Первым делом для каждого узла мы пытаемся понять – может ли он являться корнем бинарного дерева поиска (BST), то есть проверяем:
➖текущий узел больше всех узлов левого поддерева и меньше всех узлов правого поддерева

🟦Для обхода дерева используем функцию dfs, которая возвращает заготовленную структуру данных TreeData, хранящую сумму, максимальный и минимальный элементы поддерева для проверки узла на BST:

➖рекурсивно проходим до самого левого элемента, затем, поднимаясь вверх по стеку рекурсии переходим к правому поддереву, продолжая обход

➖на каждом шаге обхода делаем основную проверку на валидность BST:
▫если проверка прошла — считаем текущую сумму, используя данные левого и правого поддеревьев, и возвращаем новую TreeData для следующего шага рекурсии

▫иначе — для оптимизации алгоритма возвращаем null, поэтому в основном условии сначала проверяем, что левое и правое поддеревья не null, то есть являются BST, а затем уже проверяем текущий узел

➖для базового случая node == null, возвращаем такую TreeData, которая гарантированно сделает родителя null-узла корнем BST-поддерева, так как листья подходят под определение бинарного дерева поиска

👩‍💻 Java Algo | #solution1373