給你一個(gè)二叉樹的根節(jié)點(diǎn) root ，判斷其是否是一個(gè)有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節(jié)點(diǎn)的左子樹
只包含 小于 當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含 大于 當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。

英文題目
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 subtreeof 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.

解題思路

畫了一個(gè)四層的二叉樹，發(fā)現(xiàn)遞歸方法是，左子樹的最右節(jié)點(diǎn)應(yīng)該比根節(jié)點(diǎn)小，右子樹的最左節(jié)點(diǎn)應(yīng)該比根節(jié)點(diǎn)大，基于此寫的代碼（事實(shí)上只要想著所有點(diǎn)，然后更新邊界，就可以不用重復(fù)遍歷來遞歸了）

AC代碼

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:def judge(root):if root.left is None and root.right is None:return Trueif root is None:return Trueleft, right, leftflag, rightflag = root.left, root.right, True, Trueif left is not None:while left.right is not None:left = left.rightleftflag = root.val > left.val and judge(root.left)if right is not None:while right.left is not None:right = right.leftrightflag = root.val < right.val and judge(root.right)return  leftflag and rightflagreturn judge(root)

官方題解

想到使用邊界后面思路就一下子通了

class Solution:def isValidBST(self, root: TreeNode) -> bool:stack, inorder = [], float('-inf')while stack or root:while root:stack.append(root)root = root.leftroot = stack.pop()# 如果中序遍歷得到的節(jié)點(diǎn)的值小于等于前一個(gè) inorder，說明不是二叉搜索樹if root.val <= inorder:return Falseinorder = root.valroot = root.rightreturn True