題目描述
給定一個二叉樹篡撵，判斷其是否是一個有效的二叉搜索樹。
鏈接：https://leetcode-cn.com/problems/validate-binary-search-tree/
理解
定義
二叉搜索樹或者是一棵空樹菩鲜，或者是具有下列性質(zhì)的二叉樹：
- 若左子樹不為空，則 左子樹上所有結(jié)點的值均小于它的根結(jié)點的值
- 若右子樹不為空葵礼，則 右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
- 它的左右子樹也分別為二叉搜索樹
結(jié)論
根據(jù)以上“二叉搜索樹”的定義我們會得到以下結(jié)論：
如果采用“中序遍歷”的方式遍歷一棵“二叉搜索樹”萨醒，得到的會是一個“升序”序列。
思路
從“結(jié)論”得出的結(jié)果出發(fā)(中序遍歷后得到的數(shù)據(jù)序列是一個升序序列)写妥，“中序遍歷給定的二叉樹拳球，當(dāng)遍歷每個節(jié)點的時候，判斷當(dāng)前節(jié)點的值是否 小于等于 其前驅(qū)節(jié)點的值”
- 如果當(dāng)前節(jié)點的值“小于等于”其前驅(qū)節(jié)點的值珍特，則證明此二叉樹不是一個 二叉搜索樹祝峻。
- 否則，繼續(xù)遍歷當(dāng)前節(jié)點的左右子樹上的剩余節(jié)點扎筒。
根據(jù)“二叉搜索樹”的定義莱找，二叉搜索樹上節(jié)點的取值存在一個“范圍”，這個范圍存在一個“上限”和“下限”嗜桌。
如何確定一個節(jié)點的取值范圍呢奥溺？？骨宠？
實現(xiàn)
按照思路1中的分析谚赎，中序遍歷此二叉樹淫僻，把每個節(jié)點與其前驅(qū)節(jié)點的值進(jìn)行比較
/**
* 記錄當(dāng)前節(jié)點的前驅(qū)節(jié)點
* 每次調(diào)用“isValidBSTByInOrder()”前需要把此變量進(jìn)行重置
*/
private static TreeNode2 bsfByInOrderPreNode = null;
/**
* 采用中序遍歷,判斷訪問的"當(dāng)前結(jié)點"的值是否"小于等于"前驅(qū)結(jié)點的值
*/
public static boolean isValidBSTByInOrder(TreeNode2 node) {
if (node == null) {
return true;
}
//左子樹
if (!isValidBSTByInOrder(node.left)) {
return false;
}
//判斷當(dāng)前結(jié)點是否"小于等于"前驅(qū)結(jié)點的值
if (bsfByInOrderPreNode != null
&& node.val <= bsfByInOrderPreNode.val) {
return false;
}
//緩存前驅(qū)結(jié)點
bsfByInOrderPreNode = node;
//右子樹
return isValidBSTByInOrder(node.right);
}
