leetcode-初级-验证二叉搜索树_java 验证二叉搜索树 leetcode

题意：判断一棵树是否满足二叉搜索树。 
二叉搜索树的特点：左子树<根节点<右子树 
解题思路：中序遍历，链栈，来实现。 
对于一颗二叉树，中序遍历的结果若满足递增排序就满足二叉搜索树的条件

引用自：https://blog.csdn.net/sanmao0816/article/details/45085321

/**
 *解题思路：中序遍历，链栈
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
  * };
 */
int flag;
struct Node{//创建一个链栈节点
    int val;
    struct Node *next;
};
struct Stack{//创建一个链栈
    struct Node *top;//指向链栈栈顶节点
    int count;//记录链栈的节点个数
};
void InitStack(struct Stack *stack){//初始化一个空栈
    stack->count = 0;
    stack->top = NULL;
}
void PushStack(struct Stack *stack,int val){//压栈
    struct Node *node;
    node = (struct Node *)malloc(sizeof(struct Node));
    if(stack->count > 0){
        if(stack->top->val < val){//若不是第一个进栈的节点，则判断与栈顶节点的值大小，若小于栈顶节点值则说明不是二叉搜索树
            node->val = val;
            node->next = stack->top;
            stack->top = node;
            stack->count++;
        }else{
            flag = -1;//若不是二叉搜索树设置全局标志位flag为-1;
            return;
        }
    }else{//第一个值进栈
        node->val = val;
        node->next = stack->top;
        stack->top = node;
        stack->count++;
    }
}
void Inorder(struct TreeNode *root,struct Stack *stack){//中序遍历
    if(root == NULL){
        return;
    }
    Inorder(root->left,stack);
    PushStack(stack,root->val);
    Inorder(root->right,stack);
}
bool isValidBST(struct TreeNode *root) {
    flag = 0;
    struct Stack *stack;
    stack = (struct Stack *)malloc(sizeof(struct Stack));
    InitStack(stack);
    Inorder(root,stack);
    if(flag == -1){
        return 0;
    }
    return 1;
}

还是比较麻烦的，答案中有简单的，引用自：

https://leetcode-cn.com/submissions/detail/4298464/

bool isTree(struct TreeNode *node,int min,int max)
{
	 if (node == NULL) return true;   
    if (node->val < min || node->val > max) return false;  //超出目前子树所在范围，不算做树
    if (node->left != NULL && node->val == INT_MIN) return false;//有左子树但本身最小，不算
    if (node->right != NULL && node->val == INT_MAX) return false;//有右子树但本身最大，不算
    return isTree(node->left, min, node->val - 1) && isTree(node->right, node->val + 1, max);  //如果目前正常，去分别搜索他的左右子树，更新子树范围，作者很皮很牛逼
}
 
bool isValidBST(struct TreeNode* root) {
	if (!root)  //如果是空树，是二叉搜索树
		return true;
    if(root->left==NULL && root->right ==NULL) //如果是单元素，是二叉搜索树
        return true;
	return isTree(root, INT_MIN, INT_MAX);  //否则，正常判断
}