## 二叉搜索树 ### 定义 * 节点的左子树只包含 小于 当前节点的数。 * 节点的右子树只包含 大于 当前节点的数。 * 所有左子树和右子树自身必须也是二叉搜索树。 ### 判断平衡二叉树 ~~~ /** * 验证二叉搜索树 * 节点的左子树只包含 小于 当前节点的数。 * 节点的右子树只包含 大于 当前节点的数。 * 所有左子树和右子树自身必须也是二叉搜索树。 * @Author: mango * @Date: 2022/4/11 11:07 下午 */ public class BSTTree { public boolean isValidBST(TreeNode root) { return isBST(root).isBST; } public BSTInfo isBST(TreeNode node){ if(node == null){ return null; } BSTInfo left = isBST(node.left); BSTInfo right = isBST(node.right); int min = node.val; int max = node.val; // 找到左树和右树里的最大值和最小值 if(left != null){ min = Math.min(min,left.min); max = Math.max(max,left.max); } if(right != null){ min = Math.min(min,right.min); max = Math.max(max,right.max); } // 默认为true,找到不是bst的情况设置为false boolean isBST = true; // 左树不空，左树不是bst或者左树最大值大于等于节点的值 if(left != null && (!left.isBST || left.max >= node.val)){ isBST = false; } // 右树不空，右树不是bst或者右树最小值小于等于节点的值 if(right != null && (!right.isBST || right.min <= node.val)){ isBST = false; } return new BSTInfo(isBST,min,max); } } // 收集信息 class BSTInfo{ public boolean isBST; public int min; public int max; public BSTInfo(boolean isBST, int min,int max) { this.isBST = isBST; this.min = min; this.max = max; } } ~~~