驗(yàn)證二叉搜索樹

題目描述：給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。

假設(shè)一個(gè)二叉搜索樹具有如下特征：

• 節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。

• 節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。

• 所有左子樹和右子樹自身必須也是二叉搜索樹。

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/validate-binary-search-tree/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：遞歸法

根據(jù)二叉搜索樹的性質(zhì)，當(dāng)前節(jié)點(diǎn)左子樹的上邊界（不包含）和右子樹的下邊界（不包含）是當(dāng)前節(jié)點(diǎn)的值，所以可以用遞歸的方法來解決，遞歸過程如下：

• 根節(jié)點(diǎn)沒有父結(jié)點(diǎn)，所以第一次調(diào)用遞歸方法上下邊界使用最大最小值；

• 如果當(dāng)前節(jié)點(diǎn)為null，說明是葉子節(jié)點(diǎn)，直接返回true；

• 如果當(dāng)前節(jié)點(diǎn)的值不在上下邊界范圍內(nèi)，返回false；

• 遞歸判斷當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)是否在相應(yīng)的上線邊界范圍內(nèi)。

【每日寄語】 生命不是用來尋找答案，不是用來解決問題，它是用來愉快地生活的。與其愁眉苦臉地去工作，不如寄工作于娛樂。努力的人萬歲！