题目
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
1
2
3
4
5 输入:
2
/ \
1 3
输出: true示例 2:
1
2
3
4
5
6
7
8
9 输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
典型的递归解题思路:
函数的功能:判断一棵二叉树是否为有效BST(Binary Search Tree)
结束条件:树不满足条件 或 遍历完成
递推公式:左子树有效,右子树有效,
左子树最右(最大)节点小于根节点,右子树最左(最小)节点大于根节点,则树有效。错了,漏了一条当前节点为根节点的一整棵树的最大最小值还被上一级根节点所限制,因此,每到达一个节点,这个节点有一个区间限制,左子节点有一个区间限制,右子节点有一个区间限制,这三个区间的参数是耦合的,因此必须作为函数的参数。我们需要在DFS一棵树的过程中维持其最小值和最大值。题解实现的辅助递归函数是利用区间,递归判断根节点及其左右子节点是否在有效区间内来判断BST是否有效。
题解的思路与我的思路相比,相同之处在于都要维护最大最小值,而不同之处在于我在思考如何维护一棵子树的最大最小值时考虑用返回值保存最大最小值,判断左子树最大值与右子树最小值与根节点的大小,这意味着函数体中要实现最值的记录;
代码如下:
1 | /** |
需要注意的点:
- 为什么要用辅助递归函数?
因为原函数的作用是判断BST是否有效,递归时只能判断左右子树是否有效,不能判断根节点与左右子树之间的关系; - 边界值的类型要足够大,避免溢出;
- 左子树的范围为
(lo, root->val)
,右子树范围(root->val, hi)
,原因是BST所有元素必须在给定区间内; - 时间复杂度
O(N)
,空间复杂度O(N)
,为最差情况下树的高度。
最妙的是利用中序遍历的性质:中序遍历BST得到的一定是升序序列。时间复杂度
O(N)
,遍历BST的所有元素,每个元素访问一次;而空间复杂度为与树高呈线性关系,O(N)
。代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/**
* 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) return true;
if(!isValidBST(root->left)) return false;
if(compare.empty()) compare.push(root->val);
else if(root->val > compare.front()){
compare.pop();
compare.push(root->val);
}
else return false;
if(!isValidBST(root->right)) return false;
return true;
}
private:
queue<int> compare;
};
总结
我认为这道题最重要的点其实是意识到中序遍历的性质:中序遍历BST得到的结果是升序序列;而利用区间和递归的解法,带给我的更多是对BST有效条件必须严谨的反思。