---------------🎈🎈題目鏈接🎈🎈-------------------

二叉搜索樹

---

98. 驗證二叉搜索樹

---

解法1 笨 中序遞歸遍歷為一個數組 然后判斷數組是不是升序排列就可以

二叉搜索樹的特性：中序遍歷是單調遞增的

時間復雜度：
中序遍歷二叉搜索樹的時間復雜度為 O(n)，其中 n 是二叉樹中節點的數量。
檢查列表是否按升序排列的時間復雜度為 O(n)。
因此，總的時間復雜度為 O(n)。

空間復雜度：
存儲節點值的列表的空間復雜度為 O(n)，因為需要存儲整個樹的節點值。
遞歸調用時的棧空間復雜度取決于樹的高度，最壞情況下為 O(n)，平均情況下為 O(log n)，其中 n 是樹中的節點數量。
因此，總的空間復雜度為 O(n)。

/*** 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) {// 中序遞歸遍歷為一個數組 然后判斷數組是不是升序排列就可以List<Integer> mylist = new ArrayList<>();helper(root,mylist);for(int i = 0; i < mylist.size(); i++){if(i>0 && (long)mylist.get(i)-(long)mylist.get(i-1) <= 0){return false;}}return true;}public void helper(TreeNode root,List<Integer> mylist){if(root == null) return ;helper(root.left,mylist);mylist.add(root.val);helper(root.right,mylist);}
}

★解法2 不使用數組 遞歸法

另一個題也是這樣 530. 二叉搜索樹的最小絕對差

class Solution {TreeNode pre = null;  public boolean isValidBST(TreeNode root) {// 不用數組直接用二叉樹結構進行判斷if(root == null) return true;  // 終止條件// 中序遍歷順序 當前的和前一個進行比較boolean left = isValidBST(root.left); // 左if(pre!= null && root.val <= pre.val){ // 中return false;}pre = root;boolean right = isValidBST(root.right); //右if(left && right) return true;else return false;}
}