题目
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
字符串转TreeNode的方法
void trimLeftTrailingSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
}
void trimRightTrailingSpaces(string &input) {
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
TreeNode* stringToTreeNode(string input) {
trimLeftTrailingSpaces(input);
trimRightTrailingSpaces(input);
//input = input.substr(1, input.length() - 2);
if (!input.size()) {
return nullptr;
}
string item;
stringstream ss;
ss.str(input);
getline(ss, item, ',');
TreeNode* root = new TreeNode(stoi(item));
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (true) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
if (!getline(ss, item, ',')) {
break;
}
trimLeftTrailingSpaces(item);
if (item != "null") {
int leftNumber = stoi(item);
node->left = new TreeNode(leftNumber);
nodeQueue.push(node->left);
}
if (!getline(ss, item, ',')) {
break;
}
trimLeftTrailingSpaces(item);
if (item != "null") {
int rightNumber = stoi(item);
node->right = new TreeNode(rightNumber);
nodeQueue.push(node->right);
}
}
return root;
}
思路
1.记录子树的上界和下界,root的左子树一定小于root的值,root的右子树一定大于root的值,然后递归左子树和右子树。
class Solution {
public:
bool isValidBST(TreeNode* root, long min, long max)
{
if (root == NULL) return true;
if (root->val <= min || max <= root->val) return false;
return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);
}
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
};
2、中序遍历二叉树,并记录前继节点
class Solution2 {
TreeNode* pre = NULL;
public:
bool isValidBST(TreeNode* root)
{
if (root == NULL) return true;
TreeNode* left = root;
while (left->left != NULL)
{
left = left->left;
}
pre = left;
return isValid(root);
}
private:
bool isValid(TreeNode* root)
{
if (root == NULL) return true;
if (!isValid(root->left)) return false;
if (root != pre && root->val <= pre->val) return false;
pre = root;
return isValid(root->right);
}
};
主程序
int main() {
string line = "2,1,3";
TreeNode* root = stringToTreeNode(line);
bool ret = Solution().isValidBST(root);
string out = boolToString(ret);
cout << out << endl;
return 0;
}
网友评论