题目描述

代码

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