Leetcode刷题 树专题_l站刷题

二叉树的定义

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
1
2
3
4
5
6

98. 验证二叉搜索树

//树的左边必然比当前值小，树的右边必然比当前值大。
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,INT_MIN,INT_MAX);
    }
    //用long long防止INT_MIN-1或者INT_MAX+1溢出
    bool dfs(TreeNode* root,long long minl,long long maxl)
    {
        if(root == nullptr) return true; //空树是特殊的二叉搜索树
        if(root->val < minl || root->val >maxl) return false;//如果当前节点的值小于最小值或者大于最大值，则错误
        return dfs(root->left, minl, root->val - 1ll) && dfs(root->right, root->val+1ll, maxl);  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14