程序员面试金典 - 面试题 04.05. 合法二叉搜索树（中序遍历）

1. 题目

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:输入:2/ \1 3输出: true示例 2:输入:5/ \1 4/ \3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

2. 解题

class Solution {public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stk;TreeNode* tp, *prev = NULL;while(root || !stk.empty()){while(root){stk.push(root);root = root->left;}tp = stk.top();stk.pop();if(prev != NULL && prev->val >= tp->val)return false;prev = tp;root = tp->right;}return true;}};

递归返回子树的最小值和最大值，供上一层判断

class Solution {public:bool isValidBST(TreeNode* root) {if(!root)return true;bool ans = true;check(root,ans);return ans;}vector<int> check(TreeNode* root, bool& ans){if(!root || ans == false)return {};vector<int> l, r;l = check(root->left, ans);r = check(root->right, ans);if(l.empty() && r.empty())return {root->val, root->val};else if(!l.empty() && r.empty()){if(l[1] >= root->val)ans = false;return {l[0], root->val};}else if(l.empty() && !r.empty()){if(r[0] <= root->val)ans = false;return {root->val, r[1]};}else{if(l[1] >= root->val || r[0] <= root->val)ans = false;return {l[0], r[1]};} }};

or

class Solution {bool ans = true;long prevVal = LONG_MIN;public:bool isValidBST(TreeNode* root) {if(!root || ans == false)return true;isValidBST(root->left);if(root->val <= prevVal)ans = false;elseprevVal = root->val;isValidBST(root->right);return ans;}};