98. Validate Binary Search Tree
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.
Example 1:
2 / \ 1 3 Input: [2,1,3] Output: true
Example 2:
5 / \ 1 4 / \ 3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
验证一棵二叉树是否是二叉搜索树。二叉搜索树树需要满足左孩子小于等于根节点，根节点小于等于右孩子，本题中是严格的小于关系，所以二叉搜索树的中序遍历是严格递增的。一种解法是对二叉树中序遍历，然后检查遍历结果是否是严格递增的，这种解法很简单，不赘述了。
另外一种解法是直接用递归判断，代码如下。我们在每一次递归时，都判断当前节点是否大于最小值，且小于最大值，同时把当前节点的值递归带入。代码中没有求min和max的过程，但是每次调用的时候能正确检查，里面的奥秘需要自己体会，不太好讲。
举个例子吧，下图中节点6违反了BST的规则，虽然13所在子树是BST，但是6小于根节点10，所以不是BST。本代码是怎样判断出来的呢，首先根节点传入右孩子的约束是[10,max]，15传入左孩子的约束是[10,15]，13传入左孩子的约束是[10,13]，所以6并不属于[10,13]，不属于BST。
10
/ \
5 15
/ \
13 20
/ \
6 14
class Solution {
public:
bool helper(TreeNode* root, long long minVal, long long maxVal)
{
if (root == NULL)
return true;
if (root->val <= minVal || root->val >= maxVal)
return false;
return helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal);
}
bool isValidBST(TreeNode* root)
{
long long minVal = LLONG_MIN, maxVal = LLONG_MAX;
return helper(root, minVal, maxVal);
}
};本代码提交AC，用时13MS。
二刷。原理相同，更好理解的代码：
class Solution {
public:
bool isBST(TreeNode* root, int &max_val, int &min_val) {
if (root == NULL) {
max_val = INT_MIN;
min_val = INT_MAX;
return true;
}
// 以root为根的子树的最大和最小值
max_val = root->val;
min_val = root->val;
if (root->left == NULL && root->right == NULL) {
return true;
}
if (root->left) {
int left_max = INT_MIN, left_min = INT_MAX;
bool left_tree = isBST(root->left, left_max, left_min);
if (!left_tree || left_max >= root->val)return false;
min_val = min(min_val, left_min);
}
if (root->right) {
int right_max = INT_MIN, right_min = INT_MAX;
bool right_tree = isBST(root->right, right_max, right_min);
if (!right_tree || right_min <= root->val)return false;
max_val = max(max_val, right_max);
}
return true;
}
bool isValidBST(TreeNode* root) {
int max_val = INT_MIN, min_val = INT_MAX;
return isBST(root, max_val, min_val);
}
};本代码提交AC，用时12MS。
完整代码如下：
[cpp]
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)return "";
string ans = to_string(root->val);
if (root->left) ans += ","+serialize(root->left);
if (root->right) ans += ","+serialize(root->right);
return ans;
}
void insert(TreeNode* root, TreeNode* node) {
if (node->val < root->val) {
if (root->left == NULL)root->left = node;
else insert(root->left, node);
}
else {
if (root->right == NULL)root->right = node;
else insert(root->right, node);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "")return NULL;
TreeNode* root = NULL;
for (int start = 0, end = 0; end <= data.size(); ++end) {
if (data[end] == ‘,’ || end == data.size()) {
TreeNode* node = new TreeNode(atoi(data.substr(start, end – start).c_str()));
if (root == NULL)root = node;
else insert(root, node);
start = end + 1;
}
}
return root;
}
};
[/cpp]
本代码提交AC，用时26MS。]]>
对于函数$$f(x)=x^2-num$$，$$f'(x)=2x$$，所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$
所以我们可以初始代入$$x_n=num$$，然后不断用牛顿法，直到x*x<=num时，如果x*x==num，则num为完全平方数，否则不是。
关于牛顿法用于开放的原理介绍，