一.题目解析算法解析:我们需要知道搜索二叉树的一些性质知道这些前置的知识,来看一下子问题:每一个节点左边都是严格小于的,右边都是严格大于的我们就可以用prev存储上一次中序遍历的结果,进行深度优先遍历看一下具体的过程:二.代码编写:/** * 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 prevLONG_MIN;//全局变量,确保每一次递归都是用同一个prev bool isValidBST(TreeNode* root) { if(rootnullptr)return true;//空树也是二叉搜索树 bool curfalse; bool leftisValidBST(root-left);//左 if(root-valprev) curtrue,prevroot-val;//中 else return false; bool rightisValidBST(root-right);//右 return leftcurright; } };我们可以优化算法同理,右子树也可以这样优化后的代码/** * 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 prevLONG_MIN;//全局变量,确保每一次递归都是用同一个prev bool isValidBST(TreeNode* root) { if(rootnullptr)return true;//空树也是二叉搜索树 bool curfalse; bool leftisValidBST(root-left);//左 if(leftfalse)return false;//剪树枝 if(root-valprev) curtrue,prevroot-val;//中 else return false; if(curfalse)return false;//剪树枝 bool rightisValidBST(root-right);//右 // if(rightfalse)return false;//剪树枝,这里可以不用,因为中序右就是最后了没有其他树枝,理解为主 return leftcurright; } };