Задача: 333. Largest BST Subtree
Сложность: medium

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.
Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:
Значения в левом поддереве меньше значения их родительского (корневого) узла.
Значения в правом поддереве больше значения их родительского (корневого) узла.
Примечание: Поддерево должно включать всех своих потомков.

Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

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

1⃣Пост-упорядоченный обход дерева:
Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

2⃣Проверка условий BST для каждой ноды:
Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST:
- значение текущей ноды должно быть больше максимального значения в левом поддереве.
- значение текущей ноды должно быть меньше минимального значения в правом поддереве.
Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды).

3⃣Возврат максимального размера BST:
Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева.
В конце рекурсивного обхода верните максимальный размер BST в дереве.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class NodeValue {
    public $minNode;
    public $maxNode;
    public $maxSize;
    
    function __construct($minNode, $maxNode, $maxSize) {
        $this->minNode = $minNode;
        $this->maxNode = $maxNode;
        $this->maxSize = $maxSize;
    }
}

class Solution {
    private function largestBSTSubtreeHelper($root) {
        if ($root === null) {
            return new NodeValue(PHP_INT_MAX, PHP_INT_MIN, 0);
        }
        
        $left = $this->largestBSTSubtreeHelper($root->left);
        $right = $this->largestBSTSubtreeHelper($root->right);
        
        if ($left->maxNode < $root->val && $root->val < $right->minNode) {
            return new NodeValue(min($root->val, $left->minNode), max($root->val, $right->maxNode), 
                                 $left->maxSize + $right->maxSize + 1);
        }
        
        return new NodeValue(PHP_INT_MIN, PHP_INT_MAX, max($left->maxSize, $right->maxSize));
    }
    
    function largestBSTSubtree($root) {
        return $this->largestBSTSubtreeHelper($root)->maxSize;
    }
}

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