题目描述
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
解题思路
- 有很多种解法，最直观的为 使用中序遍历，来检查遍历后的序列是否满足二叉搜索树的定义
- 如果是合法的搜索树序列，中序遍历后，这个序列应该是递增的；否则是非法的。
C++代码
/**
* 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:
void Inorder(TreeNode* root, vector<int>& nums){
if(root != NULL){
Inorder(root -> left, nums);
nums.push_back(root -> val);
Inorder(root -> right, nums);
}
}
bool isValidBST(TreeNode* root) {`
vector<int> inorder;
if(root != NULL){
Inorder(root, inorder);
}else{
return true;
}
for(int i = 0; i < inorder.size() - 1; i++){
if(inorder[i] >= inorder[i + 1]){
return false;
}
}
return true;
}
};
0206解题思路
- 给的是一个指针，应该从树的遍历上进行考虑
- 要有转换的思想，这很明显 如果是中序遍历的话，应该会有一个递增的序列，由这个递增的序列来判读是否是正确的二叉搜索树
- 记住 二叉搜索树中序遍历后就是一个递增的序列
C++代码
/**
* 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:
vector<int> inorder;
bool isValidBST(TreeNode* root) {
if(root == NULL){
return true;
}
in_traverse(root);
for(int i = 0; i < inorder.size() - 1; i++){
if(inorder[i + 1] <= inorder[i]){
return false;
}
}
return true;
}
void in_traverse(TreeNode* root){ // 非递归遍历
stack<TreeNode*> s;
TreeNode* node = root;
while(!s.empty() || node != NULL){
while(node != NULL){
s.push(node);
node = node -> left;
}
if(!s.empty()){
node = s.top();
s.pop();
inorder.push_back(node -> val);
node = node -> right; ** // 这一点要注意，不是s.push(node -> right),这样做是没有意义的 **
}
}
}
};
