leetcode题解 98 验证二叉搜索树

Catalogue
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 解题代码

题目

给定一个二叉树,判断其是否是一个有效的二叉搜索树

一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树 示例1:
1
2
3
4
5
输入:
2
/ \
1 3
输出: true

解题思路

  • 根据二叉搜索树的特征进行解题,每个节点的左子树的值是小于当前节点中的值,每个节点右子树的值是大于当前节点中的值。
  • 二叉树搜索树根据中序遍历可以得到一个递增的序列,所以可以利用中序遍历,把所有二叉树的值都遍历出来,放入一个中,然后再出栈对元素进行比较,判断是否有序,若有序则表明是二叉搜索树,反之,则不是。

解题代码

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
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private Stack<Integer> stack;
public boolean isValidBST(TreeNode root) {
stack = new Stack<Integer>();
if (root == null) return true;
inOrder(root);
int i = stack.pop();
int j;
while(!stack.isEmpty()){
j = stack.pop();
if (j >= i) {
return false;
}
i = j;
}
return true;
}
public void inOrder(TreeNode root) {
if(root != null){
inOrder(root.left);
stack.push(root.val);
inOrder(root.right);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
if (root == null)
return true;
if (root.val <= low || root.val >= high)
return false;
return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}
}
Bagikan Komentar