[LeetCode]98. 验证二叉搜索树 （java实现）递归 dfs_java dfs递归

1. 题目

2. 读题（需要重点注意的东西）

思路1（递归1）：
注意：二叉搜索树中不能有重复元素
二叉搜索树的中序遍历是有序的，因此可以通过判断一颗树的中序遍历是否有序来判断其是否是二叉搜索树。
我们不需要通过将每一个值存在数组中再来判断是否有序，只需要在每次遍历的时候，记录上一个节点的值，与遍历的下一个节点比较，如果是有序的就继续遍历，否则返回false

---

思路2（递归2）：

核心思路： 给定一个节点与它应处的下界与上界，如果越界了，则返回false；

那么对于一颗二叉搜索树的节点来说，它的上界和下界如何确定呢？
二叉搜索树的定义如下：

• 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；

• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

• 它的左右子树也为二叉搜索树。

从定义中，我们知道：

1. 左子树上所有节点的值均小于它的根节点的值，因此，我们将根节点的值作为所有左子树节点的上界；

2. 右子树上所有节点的值均大于它的根节点的值，因此，我们将根节点的值作为所有右子树节点的下界；

然后判断每一个节点是否符合其上下界即可。

3. 解法

---------------------------------------------------解法：递归1---------------------------------------------------：

/**
 * 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 {
    double last = -Double.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        // 左子树不为空，一直走进左子树
        if(isValidBST(root.left))
            if(last < root.val){
                last = root.val;
                // 左子树为空了，遍历右子树，然后继续递归遍历左子树，即中序遍历
                return isValidBST(root.right);
            }
        return false;
    }
}
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

可能存在的问题：

---

---------------------------------------------------解法2：递归2---------------------------------------------------：

/**
 * 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 dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    private boolean dfs(TreeNode root,long left_value,long right_value){
        if(root == null) return true;
        // 判断每一个节点是否合法
        if(root.val <= left_value || root.val >= right_value) return false;
        // 递归判断左子树，递归判断右子树
        // 递归遍历左子树，将此时根节点的值作为上界
        // 递归遍历右子树，将此时根节点的值作为下界
        return dfs(root.left,left_value,root.val) && dfs(root.right,root.val,right_value);
    }
}
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

可能存在的问题：

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

• 递归

6. 总结

二叉搜索树的性质：

1. 二叉搜索树的中序遍历是有序的
2. 所有左子树节点的值小于根节点的值，所有右子树的值大于根节点的值，左右子树也是一颗二叉搜索树a