👉️ 力扣原文

题目

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

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

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

示例

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

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

分析思路1

递归：

1. 定义一个辅助函数isBST，用来递归判断每一个节点是否满足上述条件；
2. 对于每个节点，判断左子树中的所有节点是否小于该节点的值，右子树中的所有节点是否大于该节点的值，如果不满足则返回false；
3. 如果满足，继续递归判断该节点的左子树和右子树是否也满足上述条件，如果都满足，则返回true；
4. 如果有任何一个子树不满足，则直接返回false。

题解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 {public boolean isValidBST(TreeNode root) {return isBST(root, null, null);}private boolean isBST(TreeNode node, Integer min, Integer max) {if (node == null)return true;if ((min != null && node.val <= min) || (max != null && node.val >= max))return false;return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);}
}

执行结果

分析思路2

用栈来模拟中序遍历：
对于当前节点，如果它有左子树，就将左子树一直压入栈中，直到无左子树。然后弹出栈顶元素，更新中序遍历的前一个节点 inorder 的值，如果弹出的节点的值小于等于 inorder 的值，说明该树不是二叉搜索树，直接返回 false，否则将 inorder 更新为弹出的节点的值。
然后将当前节点指向它的右子树，开始下一轮中序遍历，重复以上过程，直到遍历完所有节点。

题解2

class Solution {public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<TreeNode>();double inorder = -Double.MAX_VALUE;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树if (root.val <= inorder) {return false;}inorder = root.val;root = root.right;}return true;}
}

执行结果