算法系列之驗(yàn)證二叉搜索樹(shù)

本題來(lái)自L(fǎng)eetcode，題目傳送門(mén)：「鏈接」

難度 ：中等

編程語(yǔ)言：Go

1. 題目介紹

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root  ，判斷其是否是一個(gè)有效的二叉搜索樹(shù) 。

有效二叉搜索樹(shù)定義如下
：

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

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

3. 所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。

示例 1  ：

引用自L(fǎng)eetcode

輸入：root = [2,1,3]輸出	：true

示例 2 ：

引用自L(fǎng)eetcode

輸入：root = [5,1,4,null,null,3,6]輸出：false解釋：根節(jié)點(diǎn)的值是 5 ，但是右子節(jié)點(diǎn)的值是4

提示 ：

1. 樹(shù)中節(jié)點(diǎn)數(shù)目范圍在[1, ] 內(nèi)

2. <= Node.val <=

2. 解題思路

要確保是正確的二叉搜索樹(shù)，則需要保證左小右大。如果所有父節(jié)點(diǎn)均滿(mǎn)足此要求，則二叉搜索樹(shù)合法 。

由此可以看出這是一道典型的遞歸題
。從root節(jié)點(diǎn)開(kāi)始
，如果左子樹(shù)存在，則左子樹(shù)成為判斷的子樹(shù)；同理右子樹(shù)也是一樣。

由于是二叉搜索樹(shù)
，則按照中序遍歷的方法，則打印出來(lái)的結(jié)果應(yīng)該是遞增的序列 。反映到算法上，則上一個(gè)節(jié)點(diǎn)值需要小于下一個(gè)節(jié)點(diǎn)值。

實(shí)現(xiàn)起來(lái)，先判斷左節(jié)點(diǎn)，然后判斷parent，然后判斷右節(jié)點(diǎn)
。保留上一個(gè)節(jié)點(diǎn)的值，當(dāng)判斷當(dāng)前節(jié)點(diǎn)（current parent node）的時(shí)候，比較其大小
，如果上一個(gè)節(jié)點(diǎn)值大于或者等于當(dāng)前節(jié)點(diǎn)值