Thursday, July 23, 2015

LintCode(95) 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.
Have you met this question in a real interview? 
Yes

Example
An example:
  2
 / \
1   3
   /
  4
   \
    5
The above binary tree is serialized as {2,1,3,#,#,4,#,#,5} (in level order).

分治，看看左右孩子是不是，然后看看当前是不是，按照post order走一圈就是了



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        if (!root)
            return true;
        if (!isValidBST(root->left))
            return false;
        if (!isValidBST(root->right))
            return false;
        if (root->left && root->left->val>=root->val)
            return false;
        if (root->right && root->right->val<=root->val)
            return false;
        return true;
    }
};



更正一下，这个解释错的。。。有一个test case没过，检查了一下发现是这样的：


上面的解法只是检查local的结构符合不符合，但是整体不对，




所以换一个思路，用inorder， 保证单调递增， 即， 保证当前大于左孩子，且，当前大于所有之前遍历过得最大值












 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        long val;
        long m=LONG_MIN;
        return inorder(root, val,m);
    }
    
    bool inorder(TreeNode* root, long& val, long &m){
        if (root==0){
            return true;
        }
        long left=LONG_MIN;
        if (!inorder(root->left, val,m))
            return false;
        if (root->val<=left || root->val<=m)
            return false;
        val=root->val;
        m=max(m,val);
        return inorder(root->right, val, m);
    }
};










Posted by



at





















Labels:
,

















No comments:















Post a Comment


















        

      









Subscribe to:
Post Comments (Atom)