当前位置:   article > 正文

Leetcode--验证二叉搜索树_给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

验证二叉搜索树

前言

本文的内容是我刷题时遇到的比较好的解题思路,特意记下来,并添加一些自己的思考,方便以后回顾学习。大家有兴趣的可以去看看“代码随想录”。
  • 1

题目内容

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的左子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

解题思路

递归法

该题得用中序遍历

1.确定递归函数的参数和返回类型

  • 返回类型:该题是验证,递归函数需要返回值,可以用bool类型来表示
  • 参数:需要二叉树的根节点

2.确定终止条件

  • 如果该节点为空,也可以是二叉搜索树

代码如下:

if (root == NULL) return true;
  • 1

3.确定单层递归的逻辑

  • 把前一个节点放在pre中,只有pre->val < root->val时才返回true。
class Solution {
public:
    TreeNode* pre = NULL; //用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;
        bool left = isValidBST(root->left);

        if(pre != NULL && pre->val >= root->val)
            return false;
        pre = root;

        bool right = isValidBST(root->right);
        return left && right;
    }

};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/818578
推荐阅读
相关标签
  

闽ICP备14008679号