98. Validate Binary Search Tree
Medium
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.
Example 1:
2 / \ 1 3 Input: [2,1,3] Output: true
Example 2:
5 / \ 1 4 / \ 3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
//C++: method2 22ms typedef long long ll; class Solution { public: bool inorder(TreeNode *root, ll &pre){ if(!root) return true; if(!inorder(root->left, pre)) return false; if(pre>=root->val){ return false; } pre = root->val; return inorder(root->right, pre); } bool isValidBST(TreeNode *root) { ll pre = -2147483649; return inorder(root, pre); } }; ]]></script> <script class="brush: js" type="syntaxhighlighter"><![CDATA[ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode *> stk; long long lb = (long long)(INT_MIN)-1; TreeNode* p = root; while(p){ stk.push(p); p = p->left; } while(stk.size()){ p = stk.top(); stk.pop(); if(lb>=p->val) return false; lb = p->val; if(p->right){ p = p->right; while(p){ stk.push(p); p = p->left; } } } return true; } }; //Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { long[] ret = valid(root); return (int)ret[0]==1; } long[] valid(TreeNode node){ if(node == null) return new long[]{1, Long.MAX_VALUE, Long.MIN_VALUE}; long[] l = valid(node.left); long[] r = valid(node.right); boolean isBST = (int)l[0]==1 && (int)r[0]==1 && l[2]<(long)node.val && node.val<(long)r[1]; return new long[]{isBST?1:0, Long.min(l[1], (long)node.val), Long.max((long)node.val, r[2])}; } }
No comments:
Post a Comment