Programming Skills: Validate Binary Search Tree

[題目]
https://leetcode.com/problems/validate-binary-search-tree/description/

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree 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:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

給你一個tree的root node，問你這棵樹是不是BST。

[思路]

我們知道對BST做inorder traverse會得到一個遞增的數列，這從BST的定義來看是很直觀的。
(如果覺得不直觀，可以先google一下inorder和BST的定義)
因此我們想對這個樹做inorder traverse來判斷一棵樹是否為BST。
但邏輯好的你一定會想到:
"是BST，則inorder traverse是遞增數列" 反之未必 "inorder traverse是遞增數列, 則是BST"
所以我們下面證明一下它成立 :

首先這兩句話應該很直觀可以理解:
1.如果我的left tree是BST，且此BST的max value小於我的value -->我+left tree是BST。
2.如果我的right tree是BST，且此BST的min value大於我的value --> 我+right tree是BST。

上述話再轉換一下 :

1.如果我的left tree是BST，且此BST最右下角的數小於身為inorder successor的我 --> 我+left tree是BST。

2.如果我的right tree是BST，且此BST最左下角的數大於身為inorder predecessor的我 --> 我+right tree是BST。

這1,2合起來意思就是

"若my two sub tree are BST，而且my inorder predecessor < me < my inorder successor(呈現遞增狀態) --> I am BST"

(怎麼突然中英混雜..)

接著你想，如果每個node都滿足這個條件，那整棵樹必定是BST。

所以得證"inorder traverse是遞增數列，則是BST"
搭配文章開頭說的"是BST，則inorder traverse是遞增數列"
得到結論："inorder traverse是遞增數列 <--> 是BST"
所以你寫code只要判斷任何一組人不是遞增就不是BST，都遞增就是BST。


class Solution {
public:
    TreeNode* pre;    
    bool inorder(TreeNode* root){
        if(!root) return true;
        if(!inorder(root->left)) return false;
        if(pre) 
            if(root->val <= pre->val) return false;
        pre=root;
        if(!inorder(root->right)) return false;
        return true;
        
    }
    
    
    bool isValidBST(TreeNode* root) {
        pre = NULL;
        return inorder(root);
    }
};