[lintcode]95.驗(yàn)證二叉查找樹

描述

給定一個(gè)二叉樹,判斷它是否是合法的二叉查找樹(BST)
一棵BST定義為:
節(jié)點(diǎn)的左子樹中的值要嚴(yán)格小于該節(jié)點(diǎn)的值脚仔。
節(jié)點(diǎn)的右子樹中的值要嚴(yán)格大于該節(jié)點(diǎn)的值。
左右子樹也必須是二叉查找樹舆绎。
一個(gè)節(jié)點(diǎn)的樹也是二叉查找樹鲤脏。

代碼

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        boolean result = false;
        if (root == null) {
            result = true;
        } else if (root.left == null && root.right == null){
            result = true;
        } else if (root.left == null){
            if (root.right.val > root.val){
                if (root.right.left == null || root.right.left.val > root.val){
                    result = true;
                }
            }
            result = result && isValidBST(root.right);
        } else if (root.right == null){
            if (root.left.val < root.val){
                if (root.left.right == null || root.left.right.val < root.val){
                    result = true;
                }
            }
            result = result && isValidBST(root.left);
        } else {
            boolean tmp = false;
            if (root.left.val < root.val && root.right.val > root.val){
                if (root.right.left == null || root.right.left.val > root.val){
                    result = true;
                }
                if (root.left.right == null || root.left.right.val < root.val){
                    tmp = true;
                }
            }
            result = result && tmp && isValidBST(root.left) && isValidBST(root.right);
        }

        return result;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子猎醇,更是在濱河造成了極大的恐慌窥突,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,657評(píng)論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件硫嘶,死亡現(xiàn)場(chǎng)離奇詭異波岛,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)音半,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門则拷,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人曹鸠,你說我怎么就攤上這事煌茬。” “怎么了彻桃?”我有些...
    開封第一講書人閱讀 164,057評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵坛善,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我邻眷,道長(zhǎng)眠屎,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,509評(píng)論 1 293
  • 正文 為了忘掉前任肆饶,我火速辦了婚禮改衩,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘驯镊。我一直安慰自己葫督,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,562評(píng)論 6 392
  • 文/花漫 我一把揭開白布板惑。 她就那樣靜靜地躺著橄镜,像睡著了一般。 火紅的嫁衣襯著肌膚如雪冯乘。 梳的紋絲不亂的頭發(fā)上洽胶,一...
    開封第一講書人閱讀 51,443評(píng)論 1 302
  • 那天,我揣著相機(jī)與錄音裆馒,去河邊找鬼姊氓。 笑死,一個(gè)胖子當(dāng)著我的面吹牛领追,可吹牛的內(nèi)容都是我干的他膳。 我是一名探鬼主播,決...
    沈念sama閱讀 40,251評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼绒窑,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼棕孙!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,129評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤蟀俊,失蹤者是張志新(化名)和其女友劉穎钦铺,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體肢预,經(jīng)...
    沈念sama閱讀 45,561評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡矛洞,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,779評(píng)論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了烫映。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片沼本。...
    茶點(diǎn)故事閱讀 39,902評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖锭沟,靈堂內(nèi)的尸體忽然破棺而出抽兆,到底是詐尸還是另有隱情,我是刑警寧澤族淮,帶...
    沈念sama閱讀 35,621評(píng)論 5 345
  • 正文 年R本政府宣布辫红,位于F島的核電站,受9級(jí)特大地震影響祝辣,放射性物質(zhì)發(fā)生泄漏贴妻。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,220評(píng)論 3 328
  • 文/蒙蒙 一蝙斜、第九天 我趴在偏房一處隱蔽的房頂上張望名惩。 院中可真熱鬧,春花似錦乍炉、人聲如沸绢片。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至巢株,卻和暖如春槐瑞,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背阁苞。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工困檩, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人那槽。 一個(gè)月前我還...
    沈念sama閱讀 48,025評(píng)論 2 370
  • 正文 我出身青樓悼沿,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親骚灸。 傳聞我的和親對(duì)象是個(gè)殘疾皇子糟趾,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,843評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容