题目

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

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

解法

二叉排序树有个特点是，结点通过中序遍历出来的顺序一定是从小到大的，利用这个特点我们就可以解此题。将中序遍历后的数据判断一下就OK:

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};*/

class Checker {

public:

    void inorder(TreeNode* root)

    {

        if(root==NULL)

            return ;

        inorder(root->left);

        temp.push_back(root->val);

        inorder(root->right);

    }

    bool checkBST(TreeNode* root) {

        // write code Here

        if(root==NULL)

            return true;

        inorder(root);

        for(int i=0;i<temp.size()-1;i++)

        {

            if(temp[i]>temp[i+1])

                return false;

        }

        return true;

    }

private:

    vector<int> temp;

};

还可以在中序遍历的同时，比较大小，每次记录下上次遍历过的元素的值，如果当前元素的值大于上次遍历元素的值，则接着遍历，否则返回false，因为这个记录是一个址传递，所以需要用到引用形参进行传递。见代码:

class Checker {

public:

    bool checkBST(TreeNode* root) {

        // write code here

        int min = INT_MIN;

        return inOrderCompare(root, min);

    }

    bool inOrderCompare(TreeNode* root, int &last)

    {

        if (root == NULL)

            return true;

        if (!inOrderCompare(root->left, last))

            return false;

        if (root->val < last)

            return false;

        last = root->val;

        if (!inOrderCompare(root->right, last))

            return false;

        return true;

    }

};

巴特西

CC22:检查是否为BST

题目

解法

最新文章

热门文章