美文网首页
验证搜索二叉树

验证搜索二叉树

作者: 锦绣拾年 | 来源:发表于2020-02-07 23:03 被阅读0次
给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

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

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ,但是其右子节点值为 4 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

用中序遍历可以实现
关键是怎么存前一个值。
我是用vector,但实际上直接定义一个int貌似就可??

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isvalid(TreeNode*root,vector<int> &res){
        if(root==NULL)
            return true;
        bool tmp=isvalid(root->left,res);
        if(res.size()>0){
            if(root->val<=res.back()){
                // cout<<root->val<<res.back()<<endl;
                return false;  
            }
                          
        }
        res.push_back(root->val);
        tmp=tmp&&isvalid(root->right,res);
        return tmp;
        
    }
    
    
    bool isValidBST(TreeNode* root) {
        //中序遍历是从小到大
        if(!root)
            return true;
        //int fir=root->val;
        vector<int> res;
        return isvalid(root,res);
                
    }
};

相关文章

网友评论

      本文标题:验证搜索二叉树

      本文链接:https://www.haomeiwen.com/subject/mxhbxhtx.html