做网站的大小,网站编辑器哪个好用,电工培训机构,深圳市华汇设计有限公司题目
98. 验证二叉搜索树
中等
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下#xff1a;
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当…题目
98. 验证二叉搜索树
中等
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给你一个二叉树的根节点 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
思路和解题方法 第一种方法 首先定义一个辅助函数 traversal用于实现中序遍历二叉树并将节点值存储在一个数组 vec 中。然后调用 traversal 函数来遍历二叉树并按顺序存储节点值。最后检查数组 vec 是否按照升序排列若是则为合法的二叉搜索树返回 true否则返回 false。 第二种方法 定义一个全局变量 maxVal初始值设为 LONG_MIN。使用递归函数 isValidBST 对二叉树进行深度优先搜索。在搜索过程中先递归遍历左子树然后判断当前节点的值是否大于 maxVal若是则更新 maxVal 为当前节点的值表示已经访问了当前节点继续遍历右子树。若出现当前节点的值小于等于 maxVal则说明不满足二叉搜索树的要求返回 false。如果整个搜索过程中没有出现不满足要求的情况即二叉树是合法的二叉搜索树返回 true。 第三种方法 定义一个指针 pre 用于记录前一个访问的节点。使用递归函数 isValidBST 对二叉树进行中序遍历。在中序遍历过程中先递归遍历左子树然后判断当前节点的值是否大于前一个节点的值若不满足这个条件则返回 false。如果整个中序遍历过程中都满足当前节点值大于前一个节点值的条件则说明二叉树是合法的二叉搜索树返回 true。 复杂度 时间复杂度: O(n) 时间复杂度O(n)其中 nnn 为二叉树的节点个数。二叉树的每个节点最多被访问一次因此时间复杂度为 O(n)。 空间复杂度 O(n) 空间复杂度O(n)其中 nnn 为二叉树的节点个数。栈最多存储 nnn 个节点因此需要额外的 O(n)的空间。 c 代码一
// 中序遍历二叉树将节点值按顺序存储在vec数组中
void traversal(TreeNode* root) {if(root NULL) return ;// 遍历左子树traversal(root-left);// 将当前节点值加入数组vec.push_back(root-val);// 遍历右子树traversal(root-right);
}bool isValidBST(TreeNode* root) {// 清空数组vec.clear();// 进行中序遍历traversal(root);// 检查数组是否按升序排列for(int i 1; i vec.size(); i) {// 若出现逆序则不是二叉搜索树if(vec[i] vec[i-1]) return false;}// 数组按升序排列是二叉搜索树return true;
}c代码二
long long maxVal LONG_MIN; // 因为后台测试数据中有int最小值bool isValidBST(TreeNode* root) {// 到达叶节点返回true表示是一个合法的搜索二叉树if(root NULL) return true;// 先递归处理左子树bool left isValidBST(root-left);// 判断当前节点值是否大于maxValif(maxVal root-val) maxVal root-val;else return false;// 再递归处理右子树bool right isValidBST(root-right);// 左右子树都是合法的搜索二叉树整棵树才是合法的return left right;
}c代码三
TreeNode* pre NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {// 到达叶节点返回true表示是一个合法的搜索二叉树if(root NULL) return true;// 先递归处理左子树bool left isValidBST(root-left);// 判断当前节点的值是否大于等于前一个节点的值if(pre ! NULL pre-val root-val)return false;// 更新pre指针为当前节点pre root;// 再递归处理右子树bool right isValidBST(root-right);// 左右子树都是合法的搜索二叉树整棵树才是合法的return left right;
}c迭代法
class Solution {
public:bool isValidBST(TreeNode* root) {stackTreeNode* st; // 创建一个栈用于存储节点TreeNode* cur root; // 初始化当前节点为根节点TreeNode* pre NULL; // 初始化前一个节点为NULL用于记录前一个节点的值while (cur ! NULL || !st.empty()) {if (cur ! NULL) {st.push(cur); // 将当前节点入栈cur cur-left; // 继续遍历左子树, 左} else {cur st.top(); // 弹出栈顶节点作为当前节点 中st.pop();// 判断当前节点值是否小于等于前一个节点的值如果是则不是有效的二叉搜索树if (pre ! NULL cur-val pre-val)return false;pre cur; // 更新前一个节点为当前节点cur cur-right; // 继续遍历右子树 右}}return true; // 遍历完整棵树后没有发现非法节点值返回true表示是一个有效的二叉搜索树}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
