## 二叉搜索樹 ### 定義 * 節點的左子樹只包含 小于 當前節點的數。 * 節點的右子樹只包含 大于 當前節點的數。 * 所有左子樹和右子樹自身必須也是二叉搜索樹。 ### 判斷平衡二叉樹 ~~~ /** * 驗證二叉搜索樹 * 節點的左子樹只包含 小于 當前節點的數。 * 節點的右子樹只包含 大于 當前節點的數。 * 所有左子樹和右子樹自身必須也是二叉搜索樹。 * @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; } } ~~~