这道题要判断一棵二叉树是否一棵二叉搜索树。二叉搜索树的定义是这样的：
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
我一开始的做法是这样的：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == NULL) return true; else { if (root->left != NULL && root->left->val >= root->val) { return false; } if (root->right != NULL && root->right->val <= root->val) { return false; } return isValidBST(root->left) && isValidBST(root->right); } } };
这样做很显然是错的，例子：
那应该用什么方法做呢？我们可以注意到二叉搜索树的一个性质：它的中序遍历的结果是从小到大排列的，我们可以利用到这一点：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == NULL) return true; vector<int> seq; inOrder(seq, root); for (int i = 0; i < seq.size() - 1; i++) { if (seq[i] >= seq[i + 1]) return false; } return true; } void inOrder(vector<int> &seq, TreeNode *root) { if (root == NULL) return; else { inOrder(seq, root->left); seq.push_back(root->val); inOrder(seq, root->right); } } };
很巧妙的方法，我们透过这道题要理解的就是二叉搜索树的这个性质。
[LeetCode] 98 Validate Binary Search Tree
原文：http://www.cnblogs.com/fengziwei/p/7931936.html