Validate Binary Search Tree(DFS)

时间：2014-11-09 16:38:40 收藏：0 阅读：241

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.

描述：即判断一棵树是不是二叉搜索树（左孩子小于父节点值，右孩子大于父亲节点值，且其左子树和右子树也同时满足BST）

思路：双层递归。

第一层，递归每一个节点是否满足，左边所有节点都小于它，右边所有节点都大于它。

第二层，如何来实现判断，左边所有节点都小于根，右边所有节点大于根。（每个节点都要作为根）。

特殊：root为空时，return true

代码：

class Solution {
public:
    bool isLeftValid(TreeNode *root,int val){//某个根的左树，val该根的值
        if(root==NULL) 
            return true;
        return root->val<val&&isLeftValid(root->left,val)&&isLeftValid(root->right,val);
    }
    bool isRightValid(TreeNode *root,int val){//某个根的右树，val该根的值
        if(root==NULL) 
            return true;
        return root->val>val&&isRightValid(root->left,val)&&isRightValid(root->right,val);
    }
    bool isValidBST(TreeNode *root) {
        if(root==NULL) 
            return true;
        bool flag=isLeftValid(root->left,root->val)&&isRightValid(root->right,root->val);
        if(!flag)
            return false;
        return isValidBST(root->left)&&isValidBST(root->right);
    }
};

原文：http://www.cnblogs.com/fightformylife/p/4085286.html