0x3f第七天 二叉搜索树
1.前序遍历：
4213657
先验证根是否满足大于左子树最大值，小于右子树最小值
遍历左子树（更新右值）
遍历右子树（更新左值）
对于最大值和最小值，可以直接在函数里加上
def isValidBST(self, root: Optional[TreeNode],left=-inf ,right=inf) -> bool:
先判断边界条件
if root is None:
return True
判断当前节点是否在最大最小值范围
x = root.val
if left< x < right
遍历左子树
self.isValidBST(root.left ,left ,x)更新右最大值为当前节点的val
同理遍历右子树
.....
流程是这样的，直接简写为
return left<x<right and self.isValidBST(root.left ,left ,x) and self.isValidBST(root.right ,x,right)
2.中序遍历：
1234567
先遍历左子树，再根，再右子树，符合思维逻辑，每次比较是否比上一个数大就行
我的问题：1.怎么记录上一个值
2.不能写True的情况 要写False的情况，也就是如果比上一个值大于等于
写了True，代码就结束了
3.pre为什么写在外面，更新的时候为什么是self.pre
给后面每一轮递归都提供一个pre，所以得写在外面，而且还不能写成
def isValidBST(self, root: Optional[TreeNode]，pre=-inf)
因为这个pre只有第一次递归的时候能用到，更新不了
后序遍历
1325764
首先后序遍历是 左右根
后序遍历检查搜索二叉树的根本逻辑是判断当前节点是否＞左子树的max
<右子树的min
因此引入第二个问题，怎么在递归中传递左子树的max和右子树的min
引入函数def f（node）：
if node is None:
return inf, -inf
这样叶子结点就有了它的初始左子树max和右子树min
接下来就是递归这个函数，并修改 这个元祖（ ， ）
lmin,lmax存储左子树的值
lmin,lmax=f(node.left)
rmin,rmax存储右子树的值
rmin,rmax=f(node.right)
处理当前节点：
x = node.val
先写False的情况，那就是不满足上面那个根本逻辑
if x <= l_max or x >= r_min:
return -inf, inf无效标记
else:满足，更新左max，右min
return max(lmax,x),min(rmin,x)
return f(root)[1] != inf或者return f(root)[0] != -inf 这是lmax和rmin的无效标记
【inf, -inf】 = True：表示空集，所以子树形成的集合对父节点没有约束 【-inf, inf】 = False ：全集，父节点无论如何不可能有
LCA二叉树最近公共祖先：
1.需要子树信息，告诉父节点是否有目标p，q -> 所以是后序遍历
2.边界问题： 对于None，对于p ， 对于q
左遍历右遍历
这两步遍历不做任何决策，只负责 “跑腿收集信息”，给当前节点的判断提供依据。
3.对于当前节点的决策逻辑操作： 如果 if left and right
规则含义：如果左子树找到了有效节点（非 None）、且右子树也找到了有效节点（非 None）→ 说明 p/q 分别在我（当前节点）的左右两侧，我就是它们的 “最近公共祖先”
if left is None：
return right 向下一层递归提供依据
普通二叉树的 LCA 需要遍历到空节点才能确定 “子树无 p/q”，但 BST 的特性让递归在找到 LCA 时直接返回，不会走到空节点
LCA搜索二叉树最近公共祖先
二叉搜索树的特性：
如果要找的值都小于当前节点，那就递归左子树
反之，递归右子树
如果都不是那就只剩三种情况1.此节点为p2.此节点为q3.此节点为祖先
直接return root就是