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

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

難度：中等

編程語言：Go

1. 題目介紹

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

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

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

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

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

示例 1 ：

引用自Leetcode

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

示例 2：

引用自Leetcode

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

提示：

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

2. <= Node.val <=

2. 解題思路

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

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

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

實(shí)現(xiàn)起來 ，先判斷左節(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)值，則返回false。

這種方法下 ：

1. 每一個(gè)元素需要一次遍歷 ，時(shí)間復(fù)雜度為O(n)；

2. 需要保留上一個(gè)節(jié)點(diǎn)值,空間復(fù)雜度為O(1)。（實(shí)現(xiàn)時(shí)要考慮到遞歸產(chǎn)生的方法棧，實(shí)際消耗的內(nèi)存會(huì)比較多）

3. 源碼展示

先上測(cè)試

方法實(shí)現(xiàn)

Leetcode運(yùn)算結(jié)果

• 執(zhí)行用時(shí): 8 ms
• 內(nèi)存消耗: 5 MB

生活依然要繼續(xù) ，每天拿出半個(gè)小時(shí)，放下焦慮
，用行動(dòng)來積累更好的自己
，我們一起加油