企业官网建设流程全解析

题目概览

给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

• 节点的左子树只包含严格小于当前节点的数。
• 节点的右子树只包含严格大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104]内
• -2^31 <= Node.val <= 2^31 - 1

来源：98. 验证二叉搜索树 - 力扣（LeetCode）

解题分析

方法一：递归

令当前节点为 cur，左右节点为 left 和 right，那么一定满足：

1. left 的值小于 cur 的值
2. right 的值大于 cur 的值
3. 如果 cur 的上面节点有右节点，left 的值要大于最大的右节点
4. 如果 cur 的上面节点有左节点，right 的值要小于最小的左节点

令最大右节点值和最小左节点值为 max 和 min，可得：

1. max < left < cur
2. cur < right < min

因此我们可以用递归实现，将 min 和 max 作为参数往下传即可。

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

/** * 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 isValidBST(root, Long.MAX_VALUE, Long.MIN_VALUE); } public boolean isValidBST(TreeNode root, long max, long min) { if (root == null) { return true; } if (root.val >= max || root.val <= min) { return false; } return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val); } }

方法二：中序遍历

因为中序遍历时 左-根-右 的顺序，遍历出来的数一定是递增的，因此我们只需要前后的数是否递增即可。中序遍历可以用栈来实现，这里不细讲。

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

/** * 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) { Deque<TreeNode> dq = new LinkedList<>(); long pre = Long.MIN_VALUE; while(root != null || !dq.isEmpty()) { while(root != null) { dq.push(root); root = root.left; } TreeNode node = dq.pop(); if (node.val <= pre) { return false; } pre = node.val; root = node.right; } return true; } }