首页 > 代码库 > [LeetCode]98.Validate Binary Search Tree
[LeetCode]98.Validate Binary Search Tree
【题目】
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.
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
【分析】
无
【代码】
/********************************* * 日期:2014-12-27 * 作者:SJF0115 * 题目: 98.Validate Binary Search Tree * 来源:https://oj.leetcode.com/problems/validate-binary-search-tree/ * 结果:AC * 来源:LeetCode * 总结: **********************************/ #include <iostream> #include <climits> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: bool isValidBST(TreeNode *root) { if(root == NULL){ return true; }//if return isValidBST(root,INT_MIN,INT_MAX,false,false); } private: bool isValidBST(TreeNode* node,long min,long max,bool validMin,bool validMax){ if(node == NULL){ return true; } // min max第一次不要使用 // 根节点大于左子树所有节点 小于右子树所有节点 if((validMax && node->val >= max) || (validMin && node->val <= min)){ return false; } // 左子树是否满足 bool left = isValidBST(node->left,min,node->val,validMin,true); // 右子树是否满足 bool right = isValidBST(node->right,node->val,max,true,validMax); return left && right; }// }; //按先序序列创建二叉树 int CreateBTree(TreeNode*& T){ int data; //按先序次序输入二叉树中结点的值,-1表示空树 cin>>data; if(data =http://www.mamicode.com/= -1){>
【错解】
class Solution { public: bool isValidBST(TreeNode *root) { if(root == NULL){ return true; }//if // 左子树 if(root->left){ if(root->left->val >= root->val){ return false; }//if }//if // 右子树 if(root->right){ if(root->right->val <= root->val){ return false; }//if }//if bool left = isValidBST(root->left); bool right = isValidBST(root->right); return left && right; } };10
/ \
5 15
/ \
6 20
该算法只考虑了一个根节点一个右节点一个左节点的比较,忘记了左子节点要小于父节点,小于父节点的父节点。。。。。。
右子节点要大于父节点,大于父节点的父节点。。。。。。
【错解二】
class Solution { public: bool isValidBST(TreeNode *root) { if(root == NULL){ return true; }//if return isValidBST(root,INT_MIN,INT_MAX); } private: bool isValidBST(TreeNode* node,int min,int max){ if(node == NULL){ return true; }// if(node->val >= max || node->val <= min){ return false; }//if bool left = isValidBST(node->left,min,node->val); bool right = isValidBST(node->right,node->val,max); return left && right; }// };
如果节点值等于INT边界值时就会出现问题
[LeetCode]98.Validate Binary Search Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。