10.8（98. 验证二叉搜索树 100. 相同的树）

本文主要是介绍10.8（98. 验证二叉搜索树 100. 相同的树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

98. 验证二叉搜索树

思路：

1、使用深度优先遍历的方式遍历所有的数据元素，放进vector的数组里面。
2、对数组进行排序看看是不是含有逆序对，如果有那么不正确，如果没有便是正确的。

效率：98.19%

程序代码：

class Solution {
public:bool isValidBST(TreeNode* root) {vector<int> result;Traverse(result,root);return Bubble(result);}void Traverse(vector<int> &result,TreeNode *root) {if (root == NULL)return;else {Traverse(result, root->left);result.push_back(root->val);Traverse(result, root->right);}}bool Bubble(vector<int> &result) {int n = result.size();for (int i = 0; i < n-1; i++) {if (result[i] > result[i+1])return false;}return true;}};

程序代码二：（参考答案）

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);}
};

100. 相同的树

直接采用递归的方法。

效率：100%

程序代码：

class Solution {public:bool isSameTree(TreeNode* p, TreeNode* q) {if (p == NULL && q == NULL) return true;else if(p!=NULL&&q!=NULL)return p->val == q->val&&isSameTree(p->left, p->left) && isSameTree(p->right, p->right);else return false;}};

可能出现的错误：

有时候引入了这么一句话
#include之后却显示“未定义的标识符vector”。这是因为忘记了using namespace std;

这篇关于10.8（98. 验证二叉搜索树 100. 相同的树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---