给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 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）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
本题我们依然可以利用二叉搜索树的性质来解题，二叉搜索树的中序遍历是一个升序的数组，我们可以判断相邻两个数组是否为升序关系从而判断该树是否为二叉搜索树。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
List<Integer> result = new LinkedList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 0; i < result.size() - 1; i++) {
if (result.get(i) >= result.get(i + 1)) {
return false;
}
}
return true;
}
void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
result.add(node.val);
inOrder(node.right);
}
}
|
当然了，这样做时间复杂度很爆炸，我们可以不用递归完成后再遍历数组判断是否合法，可以直接在递归的过程中判断。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
long temp = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (root.val <= temp) {
return false;
}
temp = root.val;
return isValidBST(root.right);
}
}
|
