C++实现LeetCode(98.验证二叉搜索树)
[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
这道验证二叉搜索树有很多种解法,可以利用它本身的性质来做,即左<根<右,也可以通过利用中序遍历结果为有序数列来做,下面我们先来看最简单的一种,就是利用其本身性质来做,初始化时带入系统最大值和最小值,在递归过程中换成它们自己的节点值,用long代替int就是为了包括int的边界条件,代码如下:
C++ 解法一:
// Recursion without inorder traversal class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, LONG_MIN, LONG_MAX); } bool isValidBST(TreeNode* root, long mn, long mx) { if (!root) return true; if (root->val <= mn || root->val >= mx) return false; return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx); } };
Java 解法一:
public class Solution { public boolean isValidBST(TreeNode root) { if (root == null) return true; return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean valid(TreeNode root, long low, long high) { if (root == null) return true; if (root.val <= low || root.val >= high) return false; return valid(root.left, low, root.val) && valid(root.right, root.val, high); } }
这题实际上简化了难度,因为有的时候题目中的二叉搜索树会定义为左<=根<右,而这道题设定为一般情况左<根<右,那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话,那么下边两个数用中序遍历无法区分:
20 20
/ \
20 20
它们的中序遍历结果都一样,但是左边的是 BST,右边的不是 BST。去掉等号的条件则相当于去掉了这种限制条件。下面来看使用中序遍历来做,这种方法思路很直接,通过中序遍历将所有的节点值存到一个数组里,然后再来判断这个数组是不是有序的,代码如下:
C++ 解法二:
// Recursion class Solution { public: bool isValidBST(TreeNode* root) { if (!root) return true; vector<int> vals; inorder(root, vals); for (int i = 0; i < vals.size() - 1; ++i) { if (vals[i] >= vals[i + 1]) return false; } return true; } void inorder(TreeNode* root, vector<int>& vals) { if (!root) return; inorder(root->left, vals); vals.push_back(root->val); inorder(root->right, vals); } };
Java 解法二:
public class Solution { public boolean isValidBST(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); inorder(root, list); for (int i = 0; i < list.size() - 1; ++i) { if (list.get(i) >= list.get(i + 1)) return false; } return true; } public void inorder(TreeNode node, List<Integer> list) { if (node == null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }
下面这种解法跟上面那个很类似,都是用递归的中序遍历,但不同之处是不将遍历结果存入一个数组遍历完成再比较,而是每当遍历到一个新节点时和其上一个节点比较,如果不大于上一个节点那么则返回 false,全部遍历完成后返回 true。代码如下:
C++ 解法三:
class Solution { public: bool isValidBST(TreeNode* root) { TreeNode *pre = NULL; return inorder(root, pre); } bool inorder(TreeNode* node, TreeNode*& pre) { if (!node) return true; bool res = inorder(node->left, pre); if (!res) return false; if (pre) { if (node->val <= pre->val) return false; } pre = node; return inorder(node->right, pre); } };
当然这道题也可以用非递归来做,需要用到栈,因为中序遍历可以非递归来实现,所以只要在其上面稍加改动便可,代码如下:
C++ 解法四:
class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> s; TreeNode *p = root, *pre = NULL; while (p || !s.empty()) { while (p) { s.push(p); p = p->left; } p = s.top(); s.pop(); if (pre && p->val <= pre->val) return false; pre = p; p = p->right; } return true; } };
Java 解法四:
public class Solution { public boolean isValidBST(TreeNode root) { Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode p = root, pre = null; while (p != null || !s.empty()) { while (p != null) { s.push(p); p = p.left; } p = s.pop(); if (pre != null && p.val <= pre.val) return false; pre = p; p = p.right; } return true; } }
最后还有一种方法,由于中序遍历还有非递归且无栈的实现方法,称之为 Morris 遍历,可以参考博主之前的博客 Binary Tree Inorder Traversal,这种实现方法虽然写起来比递归版本要复杂的多,但是好处在于是 O(1) 空间复杂度,参见代码如下:
C++ 解法五:
class Solution { public: bool isValidBST(TreeNode *root) { if (!root) return true; TreeNode *cur = root, *pre, *parent = NULL; bool res = true; while (cur) { if (!cur->left) { if (parent && parent->val >= cur->val) res = false; parent = cur; cur = cur->right; } else { pre = cur->left; while (pre->right && pre->right != cur) pre = pre->right; if (!pre->right) { pre->right = cur; cur = cur->left; } else { pre->right = NULL; if (parent->val >= cur->val) res = false; parent = cur; cur = cur->right; } } } return res; } };
到此这篇关于C++实现LeetCode(98.验证二叉搜索树)的文章就介绍到这了,更多相关C++实现验证二叉搜索树内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25