1. Title

Give you the root node of a binary tree, root, to determine whether it is an effective binary search tree.

A valid binary search tree is defined as follows:

• The left subtree of the node only contains the number less than the current node;
• The right subtree of a node contains only the number greater than the current node;
• All left and right subtrees themselves must also be binary search trees.

1.1 example

• Example 1 1 1 :

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

• Example 2 2 2 :

• Input: root = [5, 1, 4, null, null, 3, 6]
• Output: false
• Explanation: the value of the root node is 5 5 5, but the value of the right child node is 4 4 4 .

1.2 description

• Source: LeetCode
• Link: https://leetcode-cn.com/problems/validate-binary-search-tree

1.3 restrictions

• The number of nodes in the tree ranges from [ 1 , 1 0 4 ] [1, 10^4] [1104];
• − 2 31 < = Node.val < = 2 31 − 1 -2^{31} <= \text{Node.val} <= 2^{31} - 1 −231<=Node.val<=231−1 .

2. Solution I (recursive middle order traversal)

2.1 analysis

Since this is a binary search tree, the ordinal traversal must get a monotonically increasing sequence. Therefore, it is only necessary to perform the ordinal traversal of a given binary tree, judge whether the val value of adjacent nodes meets the monotonically increasing relationship while traversing, if not, return immediately, and maintain an instance attribute self_ Validity is used to indicate whether a given binary tree is a binary search tree. After the middle order traversal returns, the instance property is returned as a result.

2.2 realization

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self._prev = float('-inf')
        self._cur = float('-inf')
        self._validity = True

    def _is_valid_bst(self, root: TreeNode):
        if not root:
            return
        self._is_valid_bst(root.left)
        self._cur = root.val
        if self._cur <= self._prev:
            self._validity = False
            return
        self._prev = root.val
        self._is_valid_bst(root.right)

    def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
        self._is_valid_bst(root)
        return self._validity


def main():
    node5 = TreeNode(6)
    node4 = TreeNode(3)
    node3 = TreeNode(4, left=node4, right=node5)
    node2 = TreeNode(1)
    node1 = TreeNode(5, left=node2, right=node3)
    root = node1
    sln = Solution()
    print(sln.is_valid_bst(root))  # False


if __name__ == '__main__':
    main()

2.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Because incremental calls implicitly use up to n n n layers, so additional O ( n ) O(n) O(n).

3. Solution II (sequential traversal in iteration)

3.1 analysis

In addition to the recursive form, the middle order traversal of binary tree also has Order traversal in binary tree in iterative form Based on the latter, the following answers can be given:

3.2 answers

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
        if not isinstance(root, TreeNode):
            return
        cursor = root
        stack = []
        prev = float('-inf')
        while True:
            if cursor:
                stack.append(cursor)
                cursor = cursor.left
            elif stack:
                node = stack.pop()
                cur = node.val
                if cur <= prev:
                    return False
                prev = node.val
                cursor = node.right
            else:
                break
        return True


def main():
    node5 = TreeNode(6)
    node4 = TreeNode(3)
    node3 = TreeNode(4, left=node4, right=node5)
    node2 = TreeNode(1)
    node1 = TreeNode(5, left=node2, right=node3)
    root = node1
    sln = Solution()
    print(sln.is_valid_bst(root))  # False


if __name__ == '__main__':
    main()

3.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Because the stack stack used by iteration will be at most n n n elements (at this time, the given binary tree is chain), so additional O ( n ) O(n) O(n).

4. Solution 3 (recursive solution based on definition)

4.1 analysis

In fact, the analysis of the above two solutions is not very rigorous, because only a binary tree is used here, which is a necessary condition for a binary search tree, that is, the sequence obtained by order traversal must be monotonically increasing; However, it is not further proved that a binary tree is a binary search tree. A sufficient condition is that the middle order ergodic sequence of the binary tree is monotonically increasing. The reason why I didn't give a rigorous analysis is that I don't know for the time being (pit to be filled:). If any friend who happens to see this solution knows, he can discuss it together in the message area.

• Author: LeetCode-Solution

Therefore, the most rigorous solution is based on the definition of binary search tree, namely:

• If the left subtree of a given binary tree is not empty, the values of all nodes on the left subtree are less than those of its root node;
• If the right subtree of a given binary tree is not empty, the values of all nodes on the right subtree are greater than those of its root node;
• The left and right subtrees of a given binary tree are also binary search trees.

This inspires us to design a recursive function_ check_ Recursive judgment by validity (root, lower, upper). The function indicates that the subtree with root as the root is considered to judge whether the values of all nodes in the subtree are within the range of (lower, upper) (note that it is an open interval). If the value val of the root node is not within the range of (lower, upper), it indicates that it does not meet the conditions and returns directly. Otherwise, we need to continue the recursive call to check whether its left and right subtrees are satisfied. If they are satisfied, it indicates that this is a binary search tree.

According to the nature of binary search tree, when recursively calling the left subtree, we need to change the upper bound to root.val, because the values of all nodes in the left subtree are less than those of its root node. Similarly, when calling the right subtree recursively, we need to change the lower bound to root.val, because the values of all nodes in the right subtree are greater than those of its root node.

The entry of recursive function call is_ check_validity(root, -inf, +inf), inf represents an infinite value.

4.2 answers

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self._validity = True

    def _check_validity(self, root: TreeNode, lower=float('-inf'), upper=float('inf')) -> Optional[bool]:
        if not isinstance(root, TreeNode):
            return
        self._check_validity(root.left, lower, root.val)
        if root.val >= upper or root.val <= lower:
            self._validity = False
            return
        self._check_validity(root.right, root.val, upper)

    def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
        self._check_validity(root)
        return self._validity


def main():
    node5 = TreeNode(6)
    node4 = TreeNode(3)
    node3 = TreeNode(4, left=node4, right=node5)
    node2 = TreeNode(1)
    node1 = TreeNode(5, left=node2, right=node3)
    root = node1
    sln = Solution()
    print(sln.is_valid_bst(root))  # False


if __name__ == '__main__':
    main()

4.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. During recursive invocation, each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Recursive functions need to allocate stack space for each layer of recursive functions in the recursive process, so additional space is required here, and the space depends on the depth of recursion, that is, the height of binary tree. In the worst case, the binary tree is a chain, and the height of the tree is n n n. Recursive deepest reach n n n layers, so the space complexity in the worst case is O ( n ) O(n) O(n) .