本文主要是介绍leetcode 题解 98. Validate Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天开始leetcode题解，又是一个没头没尾的开始，不知道能不能全部写完。
首先给大家分享一个典型的错误答案：
bool isValidBST(struct TreeNode* root) {struct TreeNode* left;struct TreeNode* right;if(root==NULL||(root->left==NULL&&root->right==NULL)) return true;while(root){left = root->left;right = root->right;if(isValidBST(left)&&isValidBST(right)){if(left!=NULL&&right!=NULL){if(root->val>left->val&&root->val<right->val) return true;else return false;}else if(left==NULL){if(root->val<right->val) return true;else return false;}else if(right==NULL){if(root->val>left->val) return true;else return false;}else return true;}else return false;}return true;
}第一反应就是递归的求解这一问题，首先判断两棵子树是不是二叉搜索树，若两棵子树都是二叉搜索树，则判断当前节点是否为二叉搜索树，但这一做法有一个问题，就是只能判断相邻层次的树是否为二叉搜索树，但对于层次不相邻的节点就无能为力了，比如其中一个测试用例就无法通过“ [10,5,15,null,null,6,20]”。
因此要解决这一问题，靠这种递归的思路是无法解决的，我也看到了一种递归的解法不过我并没有看懂。
分享一下我的做法：既然二叉搜索树满足根节点大于左子树的所有节点，小于右子树的所有节点，所以树的中序遍历一定满足数值递增这一性质。
因此对于这道题我的解法是：中序遍历二叉搜索树，得到遍历序列，从头到尾扫描序列，若出现逆序则返回false，否则返回true。
但这里在实现上要注意的一点是：使用递归的方法实现中序遍历可能在思路上比较清晰，实现起来也比较简单，但这一方法的问题在于遍历序列的存储比较复杂，同时需要借助全局变量对数据进行存储。因此这里应使用非递归的方法是对二叉树进行遍历。
二叉树的中序非递归遍历算法：
- 从根节点出发，遍历节点的左节点并入栈，若当前节点为空则停止；
- 判断当前栈是否为空，若不为空则出栈，同时遍历当前节点的右子树；
- 判断当前栈为空同时遍历指针也为空，若同时成立则算法结束；否则返回步骤1。
源码如下：
bool isValidBST(struct TreeNode* root) {if(root==NULL) return true;struct TreeNode** temp = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*100000);int* result = (int*)malloc(sizeof(int)*100000);struct TreeNode* pointer = root;int i = 0;int j = 0;int length = 0;do{while(pointer!=NULL){temp[i++] = pointer;pointer = pointer->left;}if(i!=0){pointer = temp[--i];result[length++] = pointer->val;pointer = pointer->right;}}while(pointer!=NULL||i!=0);for(i=1;i<length;i++){if(result[i-1]>=result[i]) return false;}return true;
}由于树的中序非递归遍历需要借助栈，而c语言中不像c++中有现成的stack可以使用，因此直接使用数组模拟栈的功能，其实很简单就是数据的插入或删除均在栈的底端进行即可。之所以要申请这么大，是由于测试数据中存在这么大的输入数据。
这篇关于leetcode 题解 98. Validate Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
