leetcode 98. 验证二叉搜索树 递归遍历左右子树和中序遍历 c语言解法

如题：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。示例 1: 输入:2/ \1 3 输出: true示例 2: 输入:5/ \1 4/ \3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

这道题难度一般吧，根据二叉树的性质很容易得到解法，不过需要处理好细节。

解法1：二叉树性质，节点的左子树小于它，右子树都大于它。如果简单比较左右节点，特别容易出错。因为对于某个节点而言，除了满足和父节点的规律，还需满足整个子树的规律，因此需要存在上下边界。刚开始发现这个问题，没能解决上下界的处理，参考了官方题解后才分析清楚。

对于根节点而言，上下界同为NULL，
左节点的上界为父节点，下界继承父节点NULL;
右节点的下界为父节点，上界继承自父节点NULL; 使用指针可以避免考虑INT_MIN, INT_MAX整型边界问题

下面是c语言的解法：

bool checkBST(struct TreeNode *node, int *upper, int *lower) {int ret = 1;if (upper && node->val >= *upper)return 0;if (lower && node->val <= *lower)return 0;//父节点传递和更新上下界if (node->left)ret *= checkBST(node->left, &node->val, lower);if (node->right)ret *= checkBST(node->right, upper, &node->val);return ret; } bool isValidBST(struct TreeNode* root){int ret = 1, *prev = NULL;if (!root) return 1;//根节点上下界为NULL;return checkBST(root, NULL, NULL); }

解法2：根据二叉树性质，二叉树的中序遍历得到有序序列，因此可以中序遍历二叉树，对于每一个节点，保存其前继节点的值，然后和当前节点比较即可。

下面是c语言解法：

//中序遍历 bool inOrderTraverse(struct TreeNode* root, int **prev) {int ret = 1;//遍历左子树if (root->left)if (inOrderTraverse(root->left, prev) == 0)return 0;//中间节点if (*prev)if (root->val <= *(*prev))return 0;//更新前继节点*prev = &root->val;//遍历右子树if (root->right)if (inOrderTraverse(root->right, prev) == 0)return 0;return ret; }bool isValidBST(struct TreeNode* root){int ret = 1, *prev = NULL;//特殊情况处理if (!root) return 1;//解法2return inOrderTraverse(root, &prev); }

参考资料：

=============================================================================================

Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。

总结

以上是生活随笔为你收集整理的leetcode 98. 验证二叉搜索树 递归遍历左右子树和中序遍历 c语言解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。