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.
Perform an in-order tree traversal, save all values in an array, and later check if it is sorted
There is room for space optimization in solution below
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void rec (TreeNode *root, vector<int> &v) { if (root->left != NULL) { rec(root->left,v); } v.push_back(root->val); if (root->right != NULL) { rec(root->right,v); } } bool isValidBST(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function if (root == NULL) return true; vector<int> v; rec(root,v); if (v.size() < 2) { return true; } // check if it's already sorted for (int i = 1; i < v.size(); i++) { if (v[i-1] >= v[i]) { return false; } } return true; } };Update: Jan-16-2014
http://leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
Solution#2, in space.
Note int &pre in arguments
/** * 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 inorder (TreeNode *root, int &pre) { if (root == NULL) { return true; } if (inorder(root->left,pre)) { if (pre >= root->val) { return false; } pre = root->val; return inorder(root->right,pre); } return false; } bool isValidBST(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function if (root == NULL) return true; int pre = INT_MIN; return inorder(root,pre); } };
Update: Jan-15-2015
to handle INT_MIN case
/** * 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 inorder(TreeNode *root, TreeNode *&pre) { if (root == NULL) { return true; } if (inorder(root->left,pre)) { if (pre != NULL && pre->val >= root->val) { return false; } pre = root; return inorder(root->right,pre); } return false; } bool isValidBST(TreeNode *root) { TreeNode *pre = NULL; return inorder(root,pre); } };
Java, updated Jun-24th-2018
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private TreeNode pre = null; public boolean isValidBST(TreeNode root) { if (root == null) return true; if (!isValidBST(root.left)) { return false; } if (pre == null) pre = root; else if (pre.val >= root.val) { return false; } pre = root; return isValidBST(root.right); } }
当有node的值等于MIN_VALUE或MAX_VALUE, 这算法就搞不定了。所有还是别用了
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean helper(TreeNode root, int min, int max) { if (root == null) return true; if (root.val < max && root.val > min) { return helper(root.left, min, root.val) && helper(root.right, root.val, max); } return false; } }
No comments:
Post a Comment