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