首页 > 代码库 > (树)判断二叉树是否为BST

(树)判断二叉树是否为BST

  • 题目:判断一颗二叉树是否为BST。
  • 思路:其实这个问题可以有多个解决方法。
  • 方法一:递归解决。根据BST的特性。左边的小于根节点的值,右边的大于根节点的值。并且对于每一棵子树都是如此。所以我们可以直接递归的对左右子树的值与根节点的值进行比较。左子树的值小于当前根节点的值,将当前根节点的值作为最大值传入左子树,左子树的值都小于他,递归处理;右子树的值都大于根节点的值,将根节点的值作为最小值传入右子树,右子树的值都大于他。
  • 代码:
    /**
     * 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 isValidBST(TreeNode *root) {
            return isValidBST(root, INT_MIN, INT_MAX);
        }
        bool isValidBST(TreeNode *root, int low, int high){
            if (root == NULL )
                return true;
            if (low < root->val && root->val < high)
                return (isValidBST(root->left, low, root->val) && isValidBST(root->right, root->val, high));
            else
                return false;
        }
    };

     

  • 方法二:因为BST特性,所以我们可以利用遍历方法对他进行解决。对树进行中序遍历,将结果存储在vector中,如果容器中的值是递增排序的,那么它就是BST,否则就不是。
  • 代码:
    /**
     * 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 isValidBST(TreeNode *root) {
            vector<int> res;
            isValidBST(root, res);
            int len = res.size();
            bool flag = true;
            for (int i=0; i<len-1; i++){
                if (res[i] >= res[i+1]){
                    flag = false;
                    break;
                }
            }
            return flag;
        }
        void isValidBST(TreeNode *root, vector<int> &res){
            if (root == NULL)
                return;
            
            isValidBST(root->left, res);
            res.push_back(root->val);
            isValidBST(root->right, res);
        }
    };

     

(树)判断二叉树是否为BST