LeetCode 面试经典150题 [80/150 验证二叉搜索树]


avatar
GuoYulong 2024-07-31 179

题目描述

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

复制代码
  1. 输入:root = [2,1,3]
  2. 输出:true

示例 2:

复制代码
  1. 输入:root = [5,1,4,null,null,3,6]
  2. 输出:false
  3. 解释:根节点的值是 5 ,但是右子节点的值是 4

个人C++解答


利用二叉搜索树的定义,中序遍历为升序这样的条件去判断,起初用递归按照条件来写,但是由于没考虑左右字数必须都是二叉搜索树也就是说不能只小于或大于根节点这一个条件,所以没做出来

GYL
复制代码
  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  10. * right(right) {}
  11. * };
  12. */
  13. class Solution {
  14. vector<long> vec;
  15. public:
  16. bool isValidBST(TreeNode* root) {
  17. inOrder(root);
  18. for (int i = 1; i < vec.size(); i++) {
  19. if (vec[i] - vec[i - 1] <= 0) {
  20. return false;
  21. }
  22. }
  23. return true;
  24. }
  25. void inOrder(TreeNode* root) {
  26. if(root == nullptr) return;
  27. inOrder(root->left);
  28. vec.push_back(root->val);
  29. inOrder(root->right);
  30. }
  31. };

相关阅读

注意!!!

站点域名更新!!!部分文章图片等由于域名问题无法显示!!!

通知!!!

站点域名更新!!!部分文章图片等由于域名问题无法显示!!!