98. Validate Binary Search Tree

題目連結: 98. Validate Binary Search Tree

題目描述

給定一個二元樹，請判斷它是否是一個有效的二元搜尋樹（Binary Search Tree，BST）。

一個有效的 BST 定義如下：

• 節點的左子樹只包含小於當前節點的數字。
• 節點的右子樹只包含大於當前節點的數字。
• 所有左子樹和右子樹自身也必須是二元搜尋樹。

限制條件

• 樹中節點的數量在範圍 [1, 10^4] 內。
• -2^{31} <= Node.val <= 2^{31} - 1

解題思路

為了驗證一棵二元樹是否是有效的 BST，我們可以利用中序遍歷的特性。

• 中序遍歷：對於 BST，經過中序遍歷會得到一個嚴格遞增的數列。

因此，我們可以執行一次中序遍歷，並在遍歷過程中檢查節點值是否嚴格遞增。

實作細節：

• 使用一個指標 prev 來記錄中序遍歷中前一個訪問的節點。
• 在訪問每個節點時，將當前節點的值與 prev 的值進行比較。
  • 如果當前節點的值小於或等於 prev 的值，則樹不是有效的 BST。
• 遞迴地遍歷左子樹、當前節點、右子樹。

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    bool valid(TreeNode* root, TreeNode* &prev) {
        if (!root) {
            return true;
        }

        if (!valid(root->left, prev)) {
            return false;
        }

        if (prev && prev->val >= root->val) {
            return false;
        }
        prev = root;
        return valid(root->right, prev);
    }
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return valid(root, prev);
    }
};

時間與空間複雜度分析

• 時間複雜度：O(N)，其中 N 為樹中節點的數量。
  • 分析：每個節點都被訪問一次，因此時間複雜度為線性。
• 空間複雜度：O(H)，其中 H 為樹的高度。
  • 分析：遞迴呼叫的堆疊深度等於樹的高度。在最壞的情況下（例如退化為鏈狀的樹），高度為 N，則空間複雜度為 O(N)。在平衡的樹中，高度為 log N，因此空間複雜度為 O(log N)。