LeetCode题目:Validate Binary Search Tree

By | 2012 年 11 月 7 日

就按照BST的要求进行递归,对于每一个子树,限制它的最大,最小值,如果超过则返回false。
对于根节点,最大最小都不限制;
对于第一层子节点,需要限制单边。(左子树限制最大值小于根,右子树最小值大于根);
再往下的层次需要在父节点的最大最小值限制之下,再满足由于父节点分割造成的进一步限制。

写了一个递归算法,就搞定了。时间上没有多余的计算,只不过如果栈溢出的话,需要改成循环可以解决。



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.



代码:92ms过大集合

/**
 * 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 isValid(TreeNode *root, int maxVal, int minVal, bool checkMax, bool checkMin) {
        if(NULL == root) return true;
        if(checkMax && root->val >= maxVal) return false;
        if(checkMin && root->val <= minVal) return false;
        bool leftValid = isValid(root->left, root->val, minVal, true, checkMin);
        if(!leftValid) return false;
        return isValid(root->right, maxVal, root->val, checkMax, true);
    }
    bool isValidBST(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return isValid(root,0,0,false,false);
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注