98. Validate Binary Search Tree

LeetCode medium оригинал: C# #csharp #leetcode #medium #search #tree #two-pointers

LeetCode Static

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

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

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

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

Оба поддерева — левое и правое — также должны быть бинарными деревьями поиска.

Пример:

Input: root = [2,1,3]

Output: true

C# решение

сопоставлено/оригинал

public class Solution {
    private int? prev;
    public bool IsValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }
    private bool inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int? prev;
    public bool IsValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }
    private bool inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private int? prev;
    public boolean IsValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }
    private boolean inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

JavaScript решение

сопоставлено/оригинал

var isValidBST = function (root) {
    let prev = -Infinity;
    function inorder(node) {
        if (!node) {
            return true;
        }
        if (!inorder(node.left)) {
            return false;
        }
        if (node.val <= prev) {
            return false;
        }
        prev = node.val;
        return inorder(node.right);
    }
    return inorder(root);
};

Python решение

сопоставлено/оригинал

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def inorder(root):
            if not root:
                return True
            if not inorder(root.left):
                return False
            if root.val <= self.prev:
                return False
            self.prev = root.val
            return inorder(root.right)

        self.prev = -math.inf
        return inorder(root)

Algorithm

1️⃣

Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal):

Левый -> Узел -> Правый.

Постордер:

Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий.

Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего.

2️⃣

Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым:

Вычислить список симметричного обхода inorder.

Проверить, меньше ли каждый элемент в списке inorder следующего за ним.

Постордер:

3️⃣

Нужно ли сохранять весь список симметричного обхода?

На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.