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