首页 > 代码库 > Validate Binary Search Tree

Validate Binary Search Tree

2024-07-18 04:09:55   222人阅读

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node‘s key.
  • The right subtree of a node contains only nodes with keys greater than the node‘s key.
  • Both the left and right subtrees must also be binary search trees.                                            

分析：采用递归的方法，先判断左子树和右子树是不是BST，如果不是返回false，如果左子树和右子树均为BST，那么再比较左子树最大值、根的值、右子树最小值的关系，如果左子树最大值<根值<右子树最小值，则返回true.代码如下：

 1 class Solution { 2 public: 3     bool isValidBST(TreeNode *root) { 4         if(!root) return true; 5         if(isValidBST(root->left)){ 6             int sub_max = tree_max(root->left); 7             if(sub_max >= root->val) return false; 8         }else return false; 9         if(isValidBST(root->right)){10             int sub_min = tree_min(root->right);11             if(sub_min <= root->val) return false;12         }else return false;13         return true;14     }15     int tree_max(TreeNode * root){16         if(!root) return INT_MIN;17         int tmax = root->val;18         TreeNode * p = root->right;19         while(p){20             tmax = p->val;21             p = p->right;22         }23         return tmax;24     }25     int tree_min(TreeNode * root){26         if(!root) return INT_MAX;27         int tmin = root->val;28         TreeNode * p = root->left;29         while(p){30             tmin = p->val;31             p = p->left;32         }33         return tmin;34     }35 };

 


联系
我们