深搜(验证二叉搜索树)(4)

https://blog.csdn.net/2601_95366422/article/details/159250947一.题目98. 验证二叉搜索树 - 力扣LeetCode二.思路讲解2.1 审题本题要求验证一棵二叉树是否是有效的二叉搜索树。根据定义二叉搜索树需要满足三个条件左子树所有节点的值严格小于当前节点右子树所有节点的值严格大于当前节点左右子树本身也必须都是二叉搜索树。这里的关键在于“所有”这个词意味着不能只比较当前节点与其直接孩子而是需要保证全局的有序性。2.2 思路讲解二叉搜索树有一个非常重要的性质中序遍历的结果是严格升序的。这个性质为我们提供了简洁的验证思路——我们只需要检查这棵树的中序遍历序列是否严格递增即可。那么如何在递归遍历的过程中进行验证呢我们可以声明一个全局变量或通过引用传递来记录前驱节点的值。在中序遍历的过程中每访问一个节点就将其值与记录的前驱值进行比较如果当前节点的值小于等于前驱值说明破坏了升序性质则不是二叉搜索树否则更新前驱值为当前节点值继续遍历。2.3 剪枝剪枝是递归算法中一种提前终止的优化技巧。在本题中当我们验证左子树时如果发现左子树已经不是二叉搜索树那么整棵树肯定无效无需再遍历右子树和当前节点可以直接返回false。同样在左子树有效的情况下验证当前节点时如果当前节点值不大于前驱值也无需再遍历右子树直接返回false。这种一旦发现不满足条件就立即返回的做法可以避免不必要的递归调用提高效率。剪枝的核心思想就是在递归过程中尽早排除不符合条件的分支。三.代码演示/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: long prev LONG_MIN; bool isValidBST(TreeNode* root) { //1.终止条件 if(root nullptr) return true; //2.子问题讲解 bool left isValidBST(root-left); if(left false) return false;//剪枝 if(root-val prev ) return false;//剪枝 else prev root-val; bool right isValidBST(root-right); return right; } };四.代码讲解一、递归函数设计我们定义一个递归函数isValidBST(TreeNode* root)它返回以root为根的子树是否为有效的二叉搜索树。为了在中序遍历过程中记录前一个节点的值我们使用一个全局变量prev并初始化为LONG_MIN比所有可能的节点值都小。这样第一次比较时当前节点一定大于prev保证正确性。二、递归终止条件当当前节点为空root nullptr时空树被认为是有效的二叉搜索树直接返回true。这是递归的基础情况也是递归能够顺利返回的出口。三、递归步骤分解对于非空节点按照中序遍历的顺序左-根-右进行验证递归验证左子树调用isValidBST(root-left)判断左子树是否为二叉搜索树结果存入left。这一步我们相信递归能正确完成。如果左子树无效则整棵树无效直接返回false——这就是剪枝无需再继续。验证当前节点在左子树有效的前提下检查当前节点的值是否大于前驱节点的值prev。由于二叉搜索树要求严格递增如果当前节点值 prev则破坏有序性立即返回false再次剪枝。如果大于则更新prev为当前节点值继续。递归验证右子树最后递归验证右子树并直接返回其结果。因为如果右子树有效则整体有效否则无效。通过这种左-根-右的顺序我们利用中序遍历的升序特性在一次递归遍历中完成了验证。四、剪枝优化剪枝是递归算法中提前终止的重要技巧。在本解法中剪枝体现在两处当左子树返回false时立即返回不再递归当前节点和右子树。当当前节点值不满足大于prev时立即返回不再递归右子树。 这样避免了不必要的递归调用提高了效率。五、关键细节前驱变量prev的类型使用long并初始化为LONG_MIN是为了防止节点值恰好为INT_MIN时与prev初始值相等导致误判。因为LONG_MIN小于任何int值所以第一次比较总是成立。比较条件必须用root-val prev来判断是否无效因为二叉搜索树要求严格大于。递归顺序严格遵循中序遍历确保每个节点都能与它的中序前驱比较。