一、題目

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
它的左、右子樹也分別為二叉排序樹。

二、解答

// 方法1// 前一個節點TreeNode pre = new TreeNode();public boolean isValidBST1(TreeNode root) {// 對數進行中序遍歷，如果結果是遞增，則代表是有效二叉搜索樹；否則，不是// 不用比較全部節點，只需要比較當前節點和前一個節點即可。// 如果當前節點值小于前一個節點，則不是有效二叉搜索樹；否則，是。// 遞歸判斷左子樹，然后判斷當前節點和上一個節點值，最后遞歸判斷右子樹。if(root == null){return true;}if(!isValidBST1(root.left)){return false;}// 如果當前節點值小于前一個節點，則不是有效二叉搜索樹；if(pre != null && pre.val >= root.val){return false;}// 更新前一個節點為當前節點pre = root;return isValidBST1(root.right);}// 方法2public boolean isValidBST2(TreeNode root) {return checkValidBST(root, null, null);}/* 限定以 root 為根的子樹節點必須滿足 max.val > root.val > min.val */boolean checkValidBST(TreeNode root, TreeNode min, TreeNode max) {if(root == null){return true;}// 若 root.val 不符合 max 和 min 的限制，說明不是合法 BSTif( min != null && root.val <= min.val){return false;}if(max!= null && root.val >= max.val){return false;}// 限定左子樹的最大值是 root.val，右子樹的最小值是 root.valreturn checkValidBST(root.left,min,root) && checkValidBST(root.right,root,max);}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;}}