LeetCode 98. 驗證二元搜尋樹 (Validate Binary Search Tree) Java 解法

LeetCode 98. 驗證二元搜尋樹 (Validate Binary Search Tree) Java 解法

題目描述

給定一棵二元樹，判斷其是否為有效的二元搜尋樹 (BST)。BST 定義：

• 左子樹節點鍵值 小於 根節點鍵值
• 右子樹節點鍵值 大於 根節點鍵值
• 左右子樹皆為 BST

解題思路

中序遍歷 BST 得到的序列必為嚴格遞增（無重複元素）。故可中序遍歷收集節點值至陣列，檢查是否已排序且無重複。

Java 實作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return true;
        
        ArrayList list = inorderTraversal(root);
        int[] nums = new int[list.size()];
        int[] nums1 = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
            nums1[i] = list.get(i);
        }
        Arrays.sort(nums);
        
        if (nums[0] != nums1[0]) return false;
        for (int i = 1; i < nums.length; i++) {
            if (nums1[i] != nums[i] || nums[i] == nums[i-1])
                return false;
        }
        return true;
    }
    
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList<>();
        if (root.left != null)
            list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        if (root.right != null)
            list.addAll(inorderTraversal(root.right));
        return list;
    }
}

複雜度分析

• 時間複雜度：O(n log n)（中序遍歷 O(n) + 排序 O(n log n)）
• 空間複雜度：O(n)（儲存遍歷結果與陣列）

進階優化：遞迴傳遞上下界（long min, long max）可達 O(n) 時間、O(h) 空間（h 為樹高）。