算法系列之驗證二叉搜索樹

本題來自Leetcode ，題目傳送門：「鏈接」

難度
 ：中等

編程語言  ：Go

1. 題目介紹

給你一個二叉樹的根節(jié)點 root ，判斷其是否是一個有效的二叉搜索樹。

有效二叉搜索樹定義如下 ：

1. 節(jié)點的左子樹只包含 小于 當前節(jié)點的數(shù) 。

2. 節(jié)點的右子樹只包含 大于 當前節(jié)點的數(shù)。

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

示例 1 
：

引用自Leetcode

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

示例 2：

引用自Leetcode

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

提示：

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

2. <= Node.val <=

2. 解題思路

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

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

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

實現(xiàn)起來，先判斷左節(jié)點，然后判斷parent，然后判斷右節(jié)點 。保留上一個節(jié)點的值