程序员面试金典

程序员面试金典--检查是否为BST

题目描述

请实现一个函数，检查一棵二叉树是否为二叉查找树。

给定树的根结点指针TreeNode* root，请返回一个bool，代表该树是否为二叉查找树。

 

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Checker {
public:
    bool flag; 

    int Get(TreeNode* rt){
        if(rt->left== NULL && rt->right==NULL){
            return rt->val; 
        }
        int ans = rt->val; 
        if(rt->left){
            int lr = Get(rt->left); 
            if(lr > rt->val){
                flag = false; 
            }
            ans = max(ans, lr); 
        }

        if(rt->right){
            int rg = Get(rt->right); 
            if(rt->val > rg){
                flag = false; 
            }
            ans = max(ans, rg); 
        } 
        return ans; 
    }

    bool checkBST(TreeNode* root) {
        // write code here 
        if(root == NULL){
            return true; 
        }
        flag = true; 
        Get(root); 
        return flag; 

    }
};