记录算法笔记(2025.5.17)验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]

输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]

输出：false

解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

思路：

初始化

• 创建一个栈，用于存储尚未处理的节点。

• 设置一个变量 lastTreeNode，用于记录上一个访问的节点的值。初始值为 long.MinValue，确保第一个节点的值总是大于它。

• 设置一个指针 current，初始指向根节点 root。

主循环

循环条件是：current 不为 null 或者栈不为空。这意味着还有节点需要处理。

1. 将所有左子节点压入栈：

   • 从当前节点 current 开始，沿着左子树一直向下，将所有左子节点依次压入栈中。

   • 每次将当前节点压入栈后，将 current 指向它的左子节点。

   • 这一步确保了左子树的所有节点都被处理。

2. 弹出栈顶节点并访问：

   • 当左子树的所有节点都被压入栈后，弹出栈顶节点。此时，栈顶节点是当前需要访问的节点。

   • 将弹出的节点赋值给 current。

3. 检查当前节点值是否满足BST性质：

   • 比较当前节点的值 current.val 和上一个访问的节点值 lastTreeNode。

   • 如果当前节点的值小于或等于 lastTreeNode，说明这棵树不是有效的BST，直接返回 false。

4. 更新上一个访问的节点值：

   • 将当前节点的值赋值给 lastTreeNode，以便在下一次循环中使用。

5. 转向右子树：

   • 将 current 指向当前节点的右子节点。

   • 如果当前节点没有右子节点，current 会变成 null，循环会继续从栈中弹出下一个节点（即当前节点的祖先节点的右子树）。

循环结束

• 当 current 为 null 且栈为空时，说明所有节点都已处理完毕。

• 如果在整个遍历过程中没有发现任何违反BST性质的情况，返回 true，表示这棵树是有效的BST。

代码：C#

public class Solution {

    public bool IsValidBST(TreeNode root) {

        if(root==null)

        return true;

    Stack<TreeNode> stack=new Stack<TreeNode>();

    TreeNode current=root;

    long lastTreeNode=long.MinValue;

    while(current!=null ||stack.Count>0)

    {

        //将所有左子节点存入这个栈中，而且最低下是根节点

        while(current!=null)

        {

            stack.Push(current);

            current=current.left;

        }

         //弹出栈的一个节点

         current=stack.Pop();

         //判断当前节点是否小于上一个节点，第一次进入的时候是跟最小值比，第一个节点值随便多大

         if(current.val<=lastTreeNode)

         {

            return false;

         }

         //记下当前节点的值

         lastTreeNode=current.val;

         //将当前节点转为右子树届节点

         current=current.right;

    }

    return true;

    }

}