首页 > 代码库 > leetcode[98] Validate Binary Search Tree
leetcode[98] Validate Binary Search Tree
判断给定的数是不是合法的BST。即当前节点值比他左子树大，比右子树小。
思路一：递归，考虑所有可能。
1. 为空是返回true
2. 用flag记录左子树返回的合法性。考虑左子树不空的时候，那么要根要比左子树的最右下角要大。
3. flag为真且右子树也为真则返回真。考虑右子树时，根要比右子树的最左小。
/** * Definition for binary tree * 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) return true; bool flag = true; if (root -> left != NULL) { if (root -> left -> right == NULL) { if (root -> val > root -> left -> val) flag = isValidBST(root -> left); else return false; } else { TreeNode *lr = root -> left -> right; while(lr -> right) lr = lr -> right; if (root -> val > root -> left -> val && root -> val > lr -> val) flag = isValidBST(root -> left); else return false; } } if (root -> right != NULL) { if (root -> right -> left == NULL) { if (root -> val < root -> right -> val) return flag && isValidBST(root -> right); else return false; } else { TreeNode *rl = root -> right -> left; while(rl -> left) rl = rl -> left; if (root -> val < root -> right -> val && root -> val < rl -> val) return flag && isValidBST(root -> right); else return false; } } return flag; }};
虽然AC了，写了那么长自己都觉得。。。
然后网上看了说可以设定上下限制
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public boolean isValidBST(TreeNode root) { return isBSTRec(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean isBSTRec(TreeNode root, int left, int right) { if(root == null) { return true; } if(root.val <= left || root.val >= right) { return false; } return isBSTRec(root.left, left, root.val) && isBSTRec(root.right, root.val, right); }}
思路是根据一棵树的根为a，右子树为b，那么右子树的左儿子c的值一定是大于a且小于b
但如果树的值就是最大值的时候似乎bug。确实是。临界值不行。
不过还是找到一个写的比较简单的递归：
public class Solution { public boolean isValidBST(TreeNode root) { if(root == null){ return true; } return isSubTreeLessThan(root.left, root.val) && isSubTreeGreaterThan(root.right, root.val) && isValidBST(root.left) && isValidBST(root.right); } public boolean isSubTreeLessThan(TreeNode node, int val){ if(node == null){ return true; } return node.val < val && isSubTreeLessThan(node.left, val) && isSubTreeLessThan(node.right, val); } public boolean isSubTreeGreaterThan(TreeNode node, int val){ if(node == null){ return true; } return node.val > val && isSubTreeGreaterThan(node.left, val) && isSubTreeGreaterThan(node.right, val); } }
还有一种方法是利用中序遍历得到数组，然后判断数组是不是递增的就行。用到n的空间。
很多个地方都说min和max那个可行，估计是之前的leetcode的case没有考虑到最大值。现在已经过不了了。
leetcode[98] Validate Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。