Problem :

Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:

• The left  of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1 :

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

Example 2 :

**Input: root = [5,1,4,null,null,3,6]
Output: false**

核心思維 :

1. 檢查是否為有效二元樹並利用std::numeric_limits<long>::min() 和 std::numeric_limits<long>::max() 來表示範圍為無窮大
2. 檢查是否符合二元樹的條件
3. 檢查當前節點是否為空，若為空則符合二元樹條件，回傳true
4. 檢查節點的值是否在範圍內，若不在範圍內則回傳false
5. 檢查左右子樹範圍(low, node -> left)和右子樹範圍(node -> val, high)
6. 上述過程檢查完畢後便可以確認是否為有效的二元樹

程式碼 :

class Solution {
public:
    //檢查是否為有效二元樹
    bool isValidBST(TreeNode* root) {
        //設定初始範圍
        return validate(root, std::numeric_limits<long>::min(), std::numeric_limits<long>::max());    
    }
private:
    //檢查是否符合二元樹條件
    bool validate(TreeNode* node, long low, long high){
        //如果當前節點為空，則符合二元樹條件，回傳true
        if(node == nullptr){
            return true;
        }
        //檢查節點的值是否在範圍內，若不在範圍內回傳false
        if(node -> val <= low || node -> val >= high){
            return false;
        }
        //檢查左子樹範圍(low, node -> left)和右子樹範圍(node -> val, high)
        else{
            return validate(node -> left, low, node -> val) && validate(node -> right, node -> val, high);
        }
    }
};

結論 :
透過第98題可以提升我們對二元樹定義的理解，逐一檢查確定是否為有效二元樹，二元樹容易實作，且能夠快速找到任意節點的位置，理解二元樹的概念之後可以建構出二元搜尋樹，進行有效的插入和刪除，而進階版的二元搜尋樹又包含AVL樹和紅黑樹。