leetcode算法【98】验证二叉搜索树

柔光的暖阳◎ 2023-03-01 12:44 16阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
    
    假设一个二叉搜索树具有如下特征：
    
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
    示例 1:
    
    输入:
        2
       / \
      1   3
    输出: true
    示例 2:
    
    输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。

#### 方案： ####

*  这里要小心的就是他会出一堆阈值再Integer边界的数，所以这里干脆初始值设为Long的边界值

class Solution { 
            public boolean isValidBST(TreeNode root) { 
            	//这里要小心的就是他会出一堆阈值再Integer边界的测试参数，所以这里干脆初始值设为Long的边界值
                return judge(root, Long.MAX_VALUE, Long.MIN_VALUE);
            }
            public boolean judge(TreeNode root, long max, long min) { 
                boolean jud = true;
                if (root == null) return true;
                if (root.left != null) { 
                    int tmp = root.left.val;
                    if (tmp < root.val && tmp > min) { 
                        jud = judge(root.left, root.val, min);
                        if (jud == false) return false;
                    } else { 
                        return false;
                    }
                }
                if (root.right != null) { 
                    int tmp = root.right.val;
                    if (tmp > root.val && tmp < max) { 
                        jud = judge(root.right, max, root.val);
                        if (jud == false) return false;
                    } else { 
                        return false;
                    }
                }
                return jud;
            }
        }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode