題目：

給你一個二叉樹的根節點?root?，判斷其是否是一個有效的二叉搜索樹。

有效?二叉搜索樹定義如下：

• 節點的左子樹只包含?小于?當前節點的數。
• 節點的右子樹只包含?大于?當前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜索樹。

方法一（自己想的）：BST的中序是有序的，所以將BST中序遍歷存入隊列，判斷隊列是否遞增

class Solution {public boolean isValidBST(TreeNode root) {LinkedList<Integer> queue = new LinkedList<Integer>();dfs(root,queue);int size = queue.size();if (size < 2)return true;Integer previous = queue.poll();while (!queue.isEmpty()) {Integer current = queue.poll();if (previous >= current)return false;previous = current;}return true;}public void dfs(TreeNode root, LinkedList<Integer> queue) {if (root == null)return;dfs(root.left, queue);queue.add(root.val);dfs(root.right, queue);}
}

時間復雜度 O( n )

空間復雜度?O( n )

方法二 （靈神）：思路同一，只不過沒有用隊列存儲，而是在遞歸的時候比較

class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null)return true;if (!isValidBST(root.left) || root.val <= pre)return false;pre = root.val;return isValidBST(root.right);}
}