首页 > 代码库 > LeetCode --- Validate Binary Search Tree
LeetCode --- Validate Binary Search Tree
题目链接
判断一颗二叉树是否是二叉搜索树（二叉排序树），也就是BST
如果该二叉树是BST, 那么对其中序遍历，所得序列一定是单调递增的（不考虑有重复数值的情况）
附上代码：
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 // "fa" holds the last value that has been visited
13 // "flag" is false when it(the given binary tree or its subtree) is an invalid BST
14 void InOrder(TreeNode *root, int& fa, bool& flag) {
15 if (root->left != NULL) {
16 InOrder(root->left, fa, flag);
17 }
18 if (root->val <= fa)
19 flag = false;
20 fa = root->val;
21 if (root->right != NULL) {
22 InOrder(root->right, fa, flag);
23 }
24 }
25 bool isValidBST(TreeNode *root) {
26 if (root == NULL || root->left==NULL&&root->right==NULL) return true;
27 // initialize "fa" as INT_MIN
28 // I assume that there are no tree node‘s val equals to INT_MIN
29 // and it does... (test case like this doesnt exist)
30 int fa = INT_MIN;
31 bool flag = true;
32 InOrder(root, fa, flag);
33 if (flag)
34 return true;
35 else
36 return false;
37 }
38 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。