題目
#

leetcode 98 - Validate Binary Search Tree (題目說明請點連結)

題目簡述
#

給一個二元樹的根節點 root，判斷該樹是否為有效的二元搜尋樹（BST）。
有效 BST 的定義：

節點的左子樹只包含小於該節點值的節點
節點的右子樹只包含大於該節點值的節點
左右子樹也必須是 BST

範例
#

Example 1:

Input: root = [2,1,3]
Output: true

graph TD; A[2] B[1] C[3] A --> B A --> C

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: 根節點值是 5，但右子樹包含值 3，小於 5。

graph TD; A[5] B[1] C[4] D[null] E[null] F[3] G[6] A --> B A --> C B --> D B --> E C --> F C --> G

解題思路
#

這題要求我們驗證一個二元樹是否為有效的 BST。我們可以使用遞迴的方法，通過維護每個節點的值範圍來檢查 BST 的性質。對於每個節點，其值必須在一個特定的範圍內。

解法
#

從根節點開始，設定初始範圍為 Long.MIN_VALUE 到 Long.MAX_VALUE（這題測資範圍會到int最大最小值，要開更大）
對於每個節點，檢查其值是否在當前範圍內
遞迴檢查左子樹，範圍為 (min, node.val)
遞迴檢查右子樹，範圍為 (node.val, max)
如果所有節點都符合範圍要求，返回 true

步驟
#

初始化範圍：
- 根節點的範圍：(Long.MIN_VALUE, Long.MAX_VALUE)
遞迴檢查：
- 檢查當前節點值是否在範圍內
- 如果不在範圍內，返回 false
- 遞迴檢查左子樹：範圍 (min, node.val)
- 遞迴檢查右子樹：範圍 (node.val, max)
返回結果：
- 如果所有子樹都有效，返回 true

例子說明
#

root = [5,1,4,null,null,3,6]

graph TD; A[5] B[1] C[4] D[null] E[null] F[3] G[6] A --> B A --> C B --> D B --> E C --> F C --> G

節點	當前範圍	節點值	檢查結果	說明
根節點 5	`(-∞, +∞)`	5	✓	5 在範圍內
左子節點 1	`(-∞, 5)`	1	✓	1 在範圍內
右子節點 4	`(5, +∞)`	4	✗	4 應該大於 5

最終結果： false，不是有效的 BST

問題分析：

節點 4 是節點 5 的右子節點，應該大於 5
但 4 < 5，違反了 BST 的性質
因此這棵樹不是有效的 BST

完整程式碼
#

java

/**
 * 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) {
        // 從根節點開始檢查，初始範圍為整個 long 範圍
        return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean checkBST(TreeNode node, long min, long max) {
        // 空節點視為有效的 BST
        if (node == null) {
            return true;
        }

        // 檢查當前節點值是否在範圍內
        if (!(node.val > min && node.val < max)) {
            return false;
        }

        // 遞迴檢查左子樹和右子樹
        // 左子樹的範圍：所有值都小於當前節點值
        // 右子樹的範圍：所有值都大於當前節點值
        return checkBST(node.left, min, node.val) && checkBST(node.right, node.val, max);
    }
}