98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

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

Example 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

判斷某樹是不是二元樹，要符合條件:

1. 任一個節點的左子樹的所有節點值均小於該節點自身的值
2. 任一個節點的右子樹的所有節點值均大於該節點自身的值
3. 二元搜尋樹的左子樹和右子樹也都是二元搜尋樹

那就遞迴吧。

T: O(n), S: O(1)
# Definition for a binary tree node.
# 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.last = None
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        if not self.isValidBST(root.left): return False # 左子
        
        if self.last and root.val <= self.last.val: return False # 當現在的節點跟上一個節點相比較小或相等不是二元搜尋樹(因為越後面的節點必須較大才行)
        self.last = root # 更新上一個節點的位置
        
        return self.isValidBST(root.right) # 右子

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)