Leetcode:98.验证二叉搜索树(C++)-创新互联

目录

创新互联是一家成都网站设计、做网站,提供网页设计,网站设计,网站制作,建网站,按需网站制作,网站开发公司,于2013年创立是互联行业建设者,服务者。以提升客户品牌价值为核心业务,全程参与项目的网站策划设计制作,前端开发,后台程序制作以及后期项目运营并提出专业建议和思路。

问题描述:

实现代码与解析:

递归:

原理思路:

迭代(中序):

思路原理:


问题描述:

给你一个二叉树的根节点 root,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
实现代码与解析: 递归:
class Solution {
public:
    void traversal(TreeNode* root,vector& vec)
    {
        if(root==NULL) return;
        traversal(root->left,vec);
        vec.push_back(root->val);//中序
        traversal(root->right,vec);

    }
    bool isValidBST(TreeNode* root) 
    {
        vectorvec;
        traversal(root,vec);
        for(int i=1;i=vec[i]) return false; 
        }
        return true;
    }
};
原理思路:

  根据二叉搜索树的性质,我们中序遍历转化出来的数组一定是单调递增的且没有重复元素,代码是很好写出的。

  当然也可以不用数组,直接在递归时判断出来是否有序。下面给出代码:

class Solution {
public:
    long max=LONG_MIN;
    bool isValidBST(TreeNode* root) 
    {
       if(root==NULL) return true;
       bool left=isValidBST(root->left);
       if(root->val>max) max=root->val;//更新大值
       else return false;//若不递增,不用再向右遍历了直接返回false
       bool right=isValidBST(root->right);
       return left&&right;
    }
};

  这题测试数据中有INT_MIN,所以这里我们用LONG_MIN,当然如果这里测试数据有最小的LLONG_MIN,无法找出比它还小的值,那我们就换一种方式来比较,记录前一个结点值来判断即可:

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        //当pre不为空
        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; //记录前一个结点
        bool right = isValidBST(root->right);
        return left && right;
    }
};

  其实第一次看这个题,我想的是比较左右子树与根结点的值大小来判断返回,就像这样:

if(root->val<=root->left->val||root->val>=root->right->val) return false;

后来发现,其实这样是错误的,这样只判断左右子树的根节点,而二叉搜索树是左子树所有结点都小于根结点,右子树的所有结点都大于根节点,所以不能这样写。

迭代(中序):
class Solution {
public:
    bool isValidBST(TreeNode* root) 
    {
        stackst;
        TreeNode* pre=NULL;
        while(root!=NULL||!st.empty())
        {
            if(root!=NULL)
            {
                st.push(root);
                root=root->left;
            }
            else
            {
                root=st.top();
                st.pop();
                if(pre!=NULL&&root->val<=pre->val) return false;
                pre=root;//保存结点
                root=root->right;
            }
        }
        return true;
    }
};
思路原理:

  在中序遍历的代码上做一定修改即可。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页标题:Leetcode:98.验证二叉搜索树(C++)-创新互联
分享路径:http://pwwzsj.com/article/icgge.html