leetCode.98. 验证二叉搜索树

leetCode.98. 验证二叉搜索树

题目描述

代码

/**
 * 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) {}
 * };
 */
// 我的做法是：用一个1 * 3的数组取维护每个子树
// 第一位 表示该子树是否满足二叉搜索树， 第二位 维护左子树， 第三位维护右子树
// 维护左右子树的方式：左子树是父节点与当前结点的最小值， 右子树是父节点与当前结点的最大值
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if ( !root ) return true;
        return dfs(root)[0];
    }

    vector<int> dfs( TreeNode * root ) {
        vector<int> res ({1, root->val, root->val});

        if ( root->left ) {
            auto t = dfs( root->left ) ;
            if ( !t[0] || root->val <= t[2] ) res[0] = 0;
            // 表示如果左子树中不满二叉搜索树，或者 左子树的最大值比当前结点还要大，那当前结点就不满足二叉搜索树
            res[1] = min(t[1], res[1] );// 维护新右子树的最小值时 用
            res[2] = max(t[2], res[2] );// 维护新左子树的最大值 用
        }

        if ( root->right ) {
            auto t = dfs(root->right);;
            if ( !t[0] || root->val >= t[1] ) res[0] = 0;
            res[1] = min( t[1], res[1]);
            res[2] = max( t[2], res[2]);
        }

        return res;
    }
};
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