public boolean isValidBST(TreeNode root) {
int[] minmax = new int[2];
return isBST(root, minmax);
}
public boolean isBST(TreeNode root, int[] minmax) {
if (root == null) { // 空樹也算是 BST
return true;
}
if (root.left == null && root.right == null) {
minmax[0] = root.val;
minmax[1] = root.val;
return true;
}
// 當(dāng)左子樹為空時(shí),以root為根的樹的 minLeft maxLeft 的值
int minLeft = root.val;
int maxLeft = root.val;
boolean result = true;
if (root.left != null) {
result = isBST(root.left, minmax);
if (!result) return false; // 左子樹都不是 BST了膘流，直接返回
minLeft = minmax[0];
maxLeft = minmax[1];
// 比左子樹最大值小
if (root.val <= maxLeft) {
return false;
}
}
// 當(dāng)右子樹為空時(shí)帖族，minRight、maxRight的值
int minRight = root.val;
int maxRight = root.val;
if (root.right != null) {
result = isBST(root.right, minmax);
if (!result) return false; // 右子樹都不是 BST了爆土，直接返回
minRight = minmax[0];
maxRight = minmax[1];
if (root.val >= minRight) {
return false;
}
}
// 還能到達(dá)者說明是 BST 了
minmax[0] = minLeft;
minmax[1] = maxRight; // 更改以節(jié)點(diǎn) root 為BST的最小值箭跳、最大值
return true;
}
判斷樹是否是二叉搜索樹
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門莺琳，熙熙樓的掌柜王于貴愁眉苦臉地迎上來还棱，“玉大人，你說我怎么就攤上這事惭等≌涫郑” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵咕缎，是天一觀的道長珠十。 經(jīng)常有香客問我，道長凭豪，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任晒杈，我火速辦了婚禮嫂伞，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘。我一直安慰自己帖努，他們只是感情好撰豺，可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著拼余，像睡著了一般污桦。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上匙监，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼粮揉！你這毒婦竟也來了巡李？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬榮一對(duì)情侶失蹤扶认，失蹤者是張志新（化名）和其女友劉穎侨拦，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蝠引，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡阳谍，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了螃概。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片矫夯。...
- 正文 年R本政府宣布递沪，位于F島的核電站，受9級(jí)特大地震影響综液，放射性物質(zhì)發(fā)生泄漏款慨。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一谬莹、第九天 我趴在偏房一處隱蔽的房頂上張望檩奠。 院中可真熱鬧桩了，春花似錦、人聲如沸埠戳。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽整胃。三九已至颗圣，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間屁使，已是汗流浹背在岂。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長得像共郭，于是被迫代替她去往敵國和親祠丝。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 《劍指offer》24題：Tips：如果面試題是要求處理一棵二叉樹的遍歷序列，我們可以先找到二叉樹的根節(jié)點(diǎn)尉咕，再基于...
- 簡單來說, 完全二叉樹是指按照層次進(jìn)行遍歷的時(shí)候所得到的序列與滿二叉樹相對(duì)應(yīng) 這里提供兩種思路和相應(yīng)的代碼: 1....
- 對(duì)于如下一顆樹叠蝇，如何判斷它是否符合搜索二叉樹 首先，要明白搜索二叉樹的特點(diǎn)：1年缎，根節(jié)點(diǎn)的所有左節(jié)點(diǎn)的值小于根節(jié)點(diǎn)悔捶，...
- 需求 在項(xiàng)目中需要用到不依賴Activity Context啟動(dòng)的Dialog，并且Dialog的顯示層級(jí)要在最頂...
- 作者：毛志杰 導(dǎo)讀：當(dāng)中小學(xué)生能掌握這種“以物喻人”的寫作手法時(shí)，恭喜你洲鸠，作文水平一定超越99%的同學(xué)堂淡！ 前幾天，...
