LeetCode 98. 验证二叉搜索树（C++）

1.题目如下：

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

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true
1
2

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
1
2

解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
//方法一：递归遍历
/*递归：每遍历一个内节点，都相当于遍历一个子树的根节点，这个根节点要满足大于左边界并且小于右边界。
 * 这个题的难点在于要更新左右边界使得遍历下一层的内节点时递归函数能够生效
 * 遍历左子树：左边界不用更新；右边界更新为父节点的值
 * 遍历右子树；右边界不用更新，左边界更新为父节点
 * 对于整棵树的根节点，没有父节点，所以不需要满足什么条件，他是子节点的条件生成者，用子节点来比较
 */
 
    bool isValidBST(TreeNode* root) {
        return dpTrack(root,LONG_MIN,LONG_MAX);
    }
    bool dpTrack(TreeNode* root,long long left,long long right){
        if(root==nullptr){
            return true;
        }
        if(root->val>=right||root->val<=left){
            return false;
        }
        return(dpTrack(root->left,left,root->val)&& dpTrack(root->right,root->val,right));
    }

//方法二：中序遍历栈,先通过中序遍历把得到的序列放进栈中再判断
/*
    bool isValidBST(TreeNode* root){
        stack temp;
        dpStack(root,temp);
        while(!temp.empty()){
            int s=temp.top();
            temp.pop();
            if(!temp.empty() &&s<=temp.top()){
                return false;
            }
        }
        return true;
    }
    void dpStack(TreeNode* root, stack &temp){
        if(root->left !=nullptr){
            dpStack(root->left,temp);
        }
        temp.push(root->val);

        if(root->right!=nullptr){
            dpStack(root->right,temp);
        }
    }
    */
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60