leetcode题解 98 验证二叉搜索树

数据结构
leetcode
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