山西做网站推广,网站建设使用的基本技术,欢迎进入18入口1,网站集约化建设的优势个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
http://t.csdnimg.cn/ZxuNL个人专栏#xff1a;力扣递归算法题 http://t.csdnimg.cn/ZxuNL 【C】 http://t.csdnimg.cn/c9twt 前言#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法#x…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
http://t.csdnimg.cn/ZxuNL个人专栏力扣递归算法题 http://t.csdnimg.cn/ZxuNL 【C】 http://t.csdnimg.cn/c9twt 前言这个专栏主要讲述递归递归、搜索与回溯算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 注意这道题目涉及到二叉搜索树的内容 若有不懂的可以参考下面这篇文章
数据结构二叉搜索树-CSDN博客 验证二叉搜索树
题目链接验证二叉搜索树
题目
给你一个二叉树的根节点 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 解法
题目解析
题目没什么好说的就是给我们一颗二叉树判断它是否为二叉搜索树
二叉搜索树有如下特性
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 算法原理思路讲解
解法一
依靠二叉搜索树的特性中序遍历为有序
思路创建一个全局变量 v 中序遍历整个二叉树然后再判断 v 是否有序即可 解法二
解法一虽然也可以通过但是我们没有必要连续插入
思路
因此我们可以初始化⼀个⽆穷⼩的全区变量⽤来记录中序遍历过程中的前驱结点。那么就可以在 中序遍历的过程中先判断是否和前驱结点构成递增序列然后修改前驱结点为当前结点传⼊下⼀层的递归中。 算法流程 初始化⼀个全局的变量 prev⽤来记录中序遍历过程中的前驱结点的 val 中序遍历的递归函数中 1设置递归出⼝root nullptr 的时候返回 true 2先递归判断左⼦树是否是⼆叉搜索树⽤ left 标记 3然后判断当前结点是否满⾜⼆叉搜索树的性质⽤ cur 标记 1如果当前结点的 val ⼤于 prev说明满⾜条件cur 改为 true 2如果当前结点的 val ⼩于等于 prev说明不满⾜条件cur 改为 false 4最后递归判断右⼦树是否是⼆叉搜索树⽤ right 标记 只有当 left、 cur 和 right 都是 true 的时候才返回 true。 以上思路就讲解完了大家可以先自己先做一下 代码实现
解法一
时间复杂度O(n)其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次因此时间复杂度为 O(n)。空间复杂度O(n)其中 n 为二叉树的节点个数。vector最多存储 n 个节点因此需要额外的 O(n) 的空间。
/*** 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:vectorint v;void dfs(TreeNode* root){if (root nullptr){return;}dfs(root-left);v.push_back(root-val);dfs(root-right);}bool isValidBST(TreeNode* root) {bool flag true;dfs(root);for (int i 1; i v.size(); i){if (v[i-1] v[i]){flag false;}}return flag;}
};
解法二
时间复杂度O(n)其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次因此时间复杂度为 O(n)。空间复杂度O(n)其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间所以这里需要额外的空间且该空间取决于递归的深度即二叉树的高度。最坏情况下二叉树为一条链树的高度为 n 递归最深达到 n 层故最坏情况下空间复杂度为 O(n) 。
/*** 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 {long prev LONG_MIN;
public:bool isValidBST(TreeNode* root) {if(root nullptr) return true;bool left isValidBST(root-left);// 剪枝可以不用理会若想知道自行了解if(left false) return false; // 去掉也可以通过bool cur false;if(root-val prev)cur true;// 剪枝可以不用理会若想知道自行了解if(cur false) return false;prev root-val;bool right isValidBST(root-right);return left right cur;}
};
