#98. Validate Binary Search Tree

題目描述

給你一個二元樹的root，判斷是否為二元搜尋樹。

一個二元搜尋樹的定義如下：

左邊子樹的節點只會包含小於當前節點值的節點值。
右邊子樹的節點只會包含大於當前節點值的節點值。
左右子樹同時也必須是二元搜尋樹。

限制條件

節點數量為[1, 10⁴]。
-2³¹ <= Node.val <= 2³¹ - 1

解題思路

題目既然給出了定義，那麼只要滿足定義就可以了。

任一節點值都會介於某個範圍中，舉例來說：

    4
 2     6
1 3   5 7

每個節點的範圍如下：

4: [null,　null]
2: [null,　4　]
1: [null,　2　]
3: [2　,　4　]
6: [4　,　null]
5: [4　,　6　]
7: [6　,　null]

Solution

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Helper(root,null,null);
    }
    public bool Helper(TreeNode root, int? low, int? high){        
        if(root==null) return true;        
        if(low!=null && root.val<=low) return false;
        if(high!=null && root.val>=high) return false;
        return Helper(root.left,low,root.val) && Helper(root.right,root.val,high);
    }
}

複雜度分析：

時間複雜度：O(n)。
空間複雜度：O(n)。

學習重點

Binary Search Tree