博文中会简要介绍Leetcode P0098题目分析及解题思路。
“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.
这道题有两种通用的思路，一种是通过迭代或者递归将二叉搜索树存储下来，然后在O(n)时间内判断；第二种是通过回溯法，即深度优先搜索或者纯递归，根据二叉搜索树的性质，对于某一树结点，其左子树的最大值应当小于其自身的值，而其右子树的最小值应当大于其自身的值，则每次递归返回以这一树结点为根的子树中的最小值和最大值，将两个最值传到上层。
这两种方法实际的时间复杂度是一样的，都是O(n)，但是本文主要关注第二种解法。第二种解法有两种不同实现思路，一种是递归地返回最值，在上层判断合法性，更符合纯递归性质；另一种是将当前值往下传，将其作为上下界，然后在下层判断合法性，一旦不合法即返回，更符合深度优先搜索。
回溯法（纯递归）
递归地返回最值，在上层判断合法性。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
this.traverse(root);
return this.isValid;
}
private boolean isValid = true;
private int[] traverse(TreeNode curr) {
TreeNode left = curr.left, right = curr.right;
int min = curr.val, max = curr.val;
if (left == null && right == null)
return new int[] {min, max};
if (left != null) {
int []leftInfo = this.traverse(left);
this.isValid = this.isValid && (curr.val > leftInfo[1]);
min = Math.min(min, leftInfo[0]);
}
if (right != null) {
int []rightInfo = this.traverse(right);
this.isValid = this.isValid && (curr.val < rightInfo[0]);
max = Math.max(max, rightInfo[1]);
}
return new int[] {min, max};
}
}
回溯法（深度优先搜索）
将当前值往下传，将其作为上下界，然后在下层判断合法性。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return this.validate(root, null, null);
}
private boolean validate(TreeNode curr, TreeNode lower, TreeNode upper) {
if (curr == null)
return true;
if (lower != null && curr.val <= lower.val)
return false;
if (upper != null && curr.val >= upper.val)
return false;
return (this.validate(curr.left, lower, curr) && this.validate(curr.right, curr, upper));
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
return this->Validate(root, NULL, NULL);
}
private:
bool Validate(TreeNode *curr, TreeNode *lower, TreeNode *upper) {
if (curr == NULL)
return true;
TreeNode *left = curr->left, *right = curr->right;
int val = curr->val;
if (lower != NULL && val <= lower->val)
return false;
if (upper != NULL && val >= upper->val)
return false;
return this->Validate(left, lower, curr) && this->Validate(right, curr, upper);
}
};