递归_验证二叉搜索树_C++

一.题目解析

算法解析:

我们需要知道搜索二叉树的一些性质

知道这些前置的知识,来看一下子问题:每一个节点左边都是严格小于的,右边都是严格大于的

我们就可以用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 prev=LONG_MIN;//全局变量,确保每一次递归都是用同一个prev bool isValidBST(TreeNode* root) { if(root==nullptr)return true;//空树也是二叉搜索树 bool cur=false; bool left=isValidBST(root->left);//左 if(root->val>prev) cur=true,prev=root->val;//中 else return false; bool right=isValidBST(root->right);//右 return left&&cur&&right; } };

我们可以优化算法

同理,右子树也可以这样

优化后的代码

/** * 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;//全局变量,确保每一次递归都是用同一个prev bool isValidBST(TreeNode* root) { if(root==nullptr)return true;//空树也是二叉搜索树 bool cur=false; bool left=isValidBST(root->left);//左 if(left==false)return false;//剪树枝 if(root->val>prev) cur=true,prev=root->val;//中 else return false; if(cur==false)return false;//剪树枝 bool right=isValidBST(root->right);//右 // if(right==false)return false;//剪树枝,这里可以不用,因为中序右就是最后了没有其他树枝,理解为主 return left&&cur&&right; } };