題目描述

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

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

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

示例 1：

輸入：root = [2,1,3]
輸出：true

示例 2：

輸入：root = [5,1,4,null,null,3,6]
輸出：false
解釋：根節點的值是 5 ，但是右子節點的值是 4 。

提示：
樹中節點數目范圍在$[1,10^4]$ 內
$?2^{3}1<=Node.val<=2^{3}1?1$

思考一：前序遍歷（遞歸檢測值范圍）

二叉搜索樹的根節點的值大于所有左子樹的節點，小于所有右子樹的節點。寫遞歸函數時很容易把節點值的范圍搞錯，如下圖不是二叉搜索樹：

節點41 小于祖先節點42，不滿足二叉搜索樹根節點右子樹所有節點大于根節點值條件。
因此要定義一個遞歸函數，設置上下限參數，檢測左子樹時才更新上限值，檢測右子樹時才更新下限值。
核心是為每個節點設定合法值區間：根節點的合法區間為 (-∞, +∞)，左子節點的區間上限更新為父節點值（需嚴格小于父節點），右子節點的區間下限更新為父節點值（需嚴格大于父節點），遞歸驗證所有節點是否在合法區間內。

算法過程

1. 初始化遞歸：調用輔助函數 check，傳入根節點及初始區間 (-Infinity, Infinity)（根節點無上下限約束）。
2. 遞歸終止條件：若當前節點為 null（空樹/空子樹），符合BST規則，返回 true。
3. 節點值合法性檢測：
   • 若當前節點值 <= 區間下限 或 >= 區間上限（違反“左小右大”規則），返回 false。
4. 遞歸驗證子樹：
   • 驗證左子樹：左子樹的合法區間為 (原下限, 當前節點值)（左子樹需嚴格小于當前節點）；
   • 驗證右子樹：右子樹的合法區間為 (當前節點值, 原上限)（右子樹需嚴格大于當前節點）；
   • 只有左右子樹均驗證通過，才返回 true。
5. 返回結果：遞歸回溯后，返回最終驗證結果。

時空復雜度

• 時間復雜度：O(n)，n為二叉樹節點總數。
  原因：每個節點僅被驗證1次，遞歸操作無重復遍歷，總操作次數與節點數線性相關。
• 空間復雜度：O(h)，h為二叉樹高度。
  原因：遞歸調用棧深度取決于樹高，平衡樹h=O(log n)，鏈狀樹h=O(n)。

代碼（前序遍歷版）

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
var isValidBST = function(root) {// 初始區間：根節點無上下限，用正負無窮表示return check(root, -Infinity, Infinity);
};// 輔助函數：驗證節點是否在 [low, high) 區間內（左閉右開，保證嚴格大小）
function check(node, low, high) {// 空節點符合BST規則if (!node) return true;// 節點值超出合法區間，不是BSTif (node.val <= low || node.val >= high) {return false;}// 左子樹區間更新為 [low, node.val)，右子樹更新為 [node.val, high)return check(node.left, low, node.val) && check(node.right, node.val, high);
}

思考二：中序遍歷（驗證序列嚴格遞增）

核心是利用BST的中序遍歷特性：BST的中序遍歷結果是嚴格遞增的序列（左→根→右，值依次增大）。通過中序遍歷收集節點值，再檢查序列是否嚴格遞增，即可驗證是否為有效BST。

算法過程

1. 中序遍歷收集節點值：
   • 初始化空數組 arr，用于存儲中序遍歷的節點值；
   • 遞歸執行中序遍歷：先遍歷左子樹，再將當前節點值加入 arr，最后遍歷右子樹（左→根→右）。
2. 驗證序列嚴格遞增：
   • 遍歷數組 arr，若存在任意 i 滿足 arr[i] >= arr[i+1]（非嚴格遞增），返回 false；
   • 若所有相鄰元素均滿足 arr[i] < arr[i+1]，返回 true。
3. 返回結果：返回序列驗證結果。

時空復雜度

• 時間復雜度：O(n)，n為二叉樹節點總數。
  原因：中序遍歷收集節點值需O(n)，遍歷數組驗證需O(n)，總時間為O(n)。
• 空間復雜度：O(n)（含存儲數組）。
  原因：數組 arr 需存儲所有節點值（O(n)），遞歸調用棧需O(h)，總空間由數組主導，為O(n)。
  （優化：可不用數組，用變量記錄前一個節點值，空間復雜度降至O(h)，見下方補充）

代碼（中序遍歷版，基礎版）

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
var isValidBST = function(root) {const arr = [];// 中序遍歷收集節點值inOrder(root, arr);// 驗證序列是否嚴格遞增for (let i = 0; i < arr.length - 1; i++) {if (arr[i] >= arr[i + 1]) return false;}    return true;
};// 中序遍歷：左→根→右
function inOrder(node, arr) {if (!node) return;inOrder(node.left, arr);arr.push(node.val);inOrder(node.right, arr);
}

中序遍歷優化版（無數組，O(h)空間）

var isValidBST = function(root) {let prev = -Infinity; // 記錄前一個節點值，初始為負無窮let isValid = true;   // 標記是否為有效BSTfunction inOrder(node) {if (!node || !isValid) return; // 提前終止（已判定無效）inOrder(node.left);            // 左// 驗證當前節點值是否大于前一個節點值if (node.val <= prev) {isValid = false;return;}prev = node.val;               // 更新前一個節點值（根）inOrder(node.right);           // 右}inOrder(root);return isValid;
};

兩種方法對比

方法	核心邏輯	時間復雜度	空間復雜度（基礎版）	優勢
前序遍歷（值范圍）	遞歸驗證節點合法區間	O(n)	O(h)	無額外存儲，空間更優
中序遍歷（有序性）	驗證中序序列嚴格遞增	O(n)	O(n)（數組）	邏輯直觀，易理解
中序遍歷（優化版）	實時對比前節點值	O(n)	O(h)	兼顧直觀與空間效率

適用場景：

• 若追求空間效率，優先選擇“前序遍歷（值范圍）”或“中序遍歷優化版”；
• 若追求代碼簡潔直觀，可選擇“中序遍歷（數組版）”（節點數較少時無明顯性能問題）。