leetcode98验证二叉树

验证二叉树

双层递归（时间复杂度高）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool result = true;
    //第一层递归判断是否是二叉搜索树
    void judge_tree(TreeNode* cur )
    {   
        if(cur==nullptr) return;

        if (cur->left!=nullptr ) Traversal(cur->left , cur->val ,1);
     
        if (cur->right!=nullptr ) Traversal(cur->right , cur->val ,2);
        
        judge_tree(cur->left );
        judge_tree(cur->right );

    }
    //第二层递归判断左右子树是不是都小于自己或都大于自己
    void Traversal(TreeNode* cur , int root_val , int flag) 
    {
        if(cur==nullptr) return;
        if(flag == 1)
        {
            if(cur->val >= root_val) result=false;
        }
         if(flag == 2)
        {
            if(cur->val <= root_val) result=false;
        }
        Traversal(cur->left , root_val , flag);
        Traversal(cur->right , root_val ,flag);
    }
    
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return false;
        judge_tree(root );
        return  result; 
    }
};

单层递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	//记录上一个点
    TreeNode* pre = nullptr;
    bool judge_tree(TreeNode* cur)
    {
        if(cur==nullptr) return true;
        bool left_val =  judge_tree(cur->left);
        //当前点应该比上一个大，如果小发生错误
        if(pre != nullptr && cur->val <= pre->val) return false;
        //更新当前点
        pre = cur;
        bool right_val = judge_tree(cur->right);
        return left_val&right_val;
    }
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;
        return judge_tree(root);
    }
};