LeetCode — Проверить двоичное дерево поиска

Постановка задачи

Имея корень двоичного дерева, определить, является ли оно допустимым двоичным деревом поиска (BST).

Действительный BST определяется следующим образом:

• Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
• Правое поддерево узла содержит только узлы с ключами больше ключа узла.
• И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Пример 1:

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

Пример 2:

Input: root = [5, 1, 4, null, null, 3, 6] 
Output: false 
Explanation: The root node's value is 5, but its right child's value is 4.

Ограничения

- The number of nodes in the tree is in the range [1, 10^4].
- -2^31 <= Node.val <= 2^31 - 1

Объяснение

Неправильный подход

Первый наивный подход, который придет в голову большинству из нас, состоит в том, чтобы проверять каждый узел, левый дочерний узел должен быть меньше, а правый — больше.

Но приведенное ниже дерево не является допустимым BST, поскольку узел со значением 4 находится в левом поддереве узла со значением 3.

Правильный подход

Приведенный выше подход намекает на то, что нам нужно отслеживать максимальное и минимальное значение для любого узла в его левом и правом поддеревьях.

Проверим алгоритм.

// isValidBST function
- if root == NULL
  - return true

- return checkValidBST(root, LONG_MIN, LONG_MAX)

// checkValidBST(root, min, max) function
- if root == NULL
  - return true

- if root->val <= min || root->val >= max
  - return false

- return checkValidBST(root->left, min, root->val) && checkValidBST(root->right, root->val, max)

С++ решение

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL) {
            return true;
        }

        return checkValidBST(root, LONG_MIN, LONG_MAX);
    }

    bool checkValidBST(TreeNode* root, long min, long max){
        if(root == NULL) {
            return true;
        }

        if(root->val <= min || root->val >= max) {
            return false;
        }

        return checkValidBST(root->left, min, root->val) && checkValidBST(root->right, root->val, max);
    }
};

Голанг решение

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }

    return checkValidBST(root, math.MinInt32, math.MaxInt32)
}

func checkValidBST(root *TreeNode, min, max int) bool {
    if root == nil {
        return true
    }

    if root.Val <= min || root.Val >= max {
        return false
    }

    return checkValidBST(root.Left, min, root.Val) && checkValidBST(root.Right, root.Val, max)
}

Javascript-решение

var isValidBST = function(root) {
    if( !root ) {
        return true;
    }

    return checkValidBST(root);
};

var checkValidBST = function(root, min = -Infinity, max = +Infinity) {
    if (!root) {
        return true;
    }

    if (root.val <= min || root.val >= max) {
        return false;
    }

    return checkValidBST(root.left, min, root.val) && checkValidBST(root.right, root.val, max);
}

Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.

Input: root = [2, 1, 3]

// in isValidBST function
Step 1: if root == NULL
           false

Step 2: return checkValidBST(root, LONG_MIN, LONG_MAX)

// in checkValidBST function
Step 3: if root == NULL
           false

Step 4: if root->val <= min || root->val >= max
           2 <= LONG_MIN || 2 >= LONG_MAX
           false || false
           false

Step 5: return checkValidBST(root->left, min, root->val) && checkValidBST(root->right, root->val, max)
        return checkValidBST(1, LONG_MIN, 2) && checkValidBST(3, 2, LONG_MAX)

// checkValidBST(1, LONG_MIN, 2)
Step 6: if root == NULL
           false

Step 7: if root->val <= min || root->val >= max
           1 <= LONG_MIN || 1 >= 2
           false || false
           false

Step 8: return checkValidBST(root->left, min, root->val) && checkValidBST(root->right, root->val, max)
        return checkValidBST(null, LONG_MIN, 1) && checkValidBST(null, 1, LONG_MAX)

// checkValidBST(3, 2, LONG_MAX)
Step 9: if root == NULL
           false

Step 10: if root->val <= min || root->val >= max
            2 <= LONG_MIN || 2 >= LONG_MAX
            false || false
            false

Step 11: return checkValidBST(root->left, min, root->val) && checkValidBST(root->right, root->val, max)
         return checkValidBST(null, LONG_MIN, 3) && checkValidBST(null, 3, LONG_MAX)

Now for all the conditions
Step 7: checkValidBST(null, LONG_MIN, 1) && checkValidBST(null, 1, LONG_MAX)
Step 11: checkValidBST(null, LONG_MIN, 3) && checkValidBST(null, 3, LONG_MAX)

the first parameter root is null

So it returns true.

Hence the final answer we return is true.

Первоначально опубликовано на https://alkeshghorpade.me.