Leetcode - Closest Binary Search Tree Value II

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> st = new Stack<TreeNode>();
        Stack<TreeNode> pre = new Stack<TreeNode>();
        Stack<TreeNode> suc = new Stack<TreeNode>();
        
        TreeNode p = root;
        while (p != null) {
            st.push(p);
            p = p.left;
        }
        
        while (!st.isEmpty()) {
            p = st.pop();
            if (p.val > target) {
                break;
            }
            pre.push(p);
            if (p.right != null) {
                p = p.right;
                while (p != null) {
                    st.push(p);
                    p = p.left;
                }
            }
        }
        
        st.clear();
        
        p = root;
        while (p != null) {
            st.push(p);
            p = p.right;
        }
        
        while (!st.isEmpty()) {
            p = st.pop();
            if (p.val <= target) {
                break;
            }
            suc.push(p);
            if (p.left != null) {
                p = p.left;
                while (p != null) {
                    st.push(p);
                    p = p.right;
                }
            }
        }
        
        List<Integer> ret = new ArrayList<Integer>();
        while (k > 0) {
            if (pre.isEmpty()) {
                ret.add(suc.pop().val);
            }
            else if (suc.isEmpty()) {
                ret.add(pre.pop().val);
            }
            else if (Math.abs(pre.peek().val - target) < Math.abs(suc.peek().val - target)) {
                ret.add(pre.pop().val);
            }
            else {
                ret.add(suc.pop().val);
            }
            k--;
        }
        
        return ret;
    }
}

reference:
https://discuss.leetcode.com/topic/22940/ac-clean-java-solution-using-two-stacks/2

沒能自己做出來荸频×庑ぃ看了解析,覺得思路是那么的理所當(dāng)然旭从,竟然沒想出來稳强。场仲。。
他給的答案是recursion
我重寫了一個(gè) iteration的方法退疫,都差不多渠缕。

一個(gè)注意點(diǎn)是,
如果 pre 的break條件是 val > target

那么 suc 的break條件必須是 val <= target
不能是 val < target

否則褒繁,會(huì)把相同的數(shù)字放進(jìn)兩個(gè)棧中亦鳞,造成錯(cuò)誤的結(jié)果。

以后再給你一個(gè)binary search tree,的確可以用這種雙棧的辦法棒坏,實(shí)現(xiàn)雙指針燕差,從中間往左右掃描。

Anyway, Good luck, Richardo! -- 09/07/2016

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末坝冕,一起剝皮案震驚了整個(gè)濱河市徒探,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌喂窟,老刑警劉巖测暗,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異谎替,居然都是意外死亡偷溺,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門钱贯,熙熙樓的掌柜王于貴愁眉苦臉地迎上來挫掏,“玉大人,你說我怎么就攤上這事秩命∥竟玻” “怎么了?”我有些...
    開封第一講書人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵弃锐,是天一觀的道長袄友。 經(jīng)常有香客問我,道長霹菊,這世上最難降的妖魔是什么剧蚣? 我笑而不...
    開封第一講書人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮旋廷,結(jié)果婚禮上鸠按,老公的妹妹穿的比我還像新娘。我一直安慰自己饶碘,他們只是感情好目尖,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著扎运,像睡著了一般瑟曲。 火紅的嫁衣襯著肌膚如雪饮戳。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評(píng)論 1 312
  • 那天洞拨,我揣著相機(jī)與錄音扯罐,去河邊找鬼。 笑死烦衣,一個(gè)胖子當(dāng)著我的面吹牛篮赢,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播琉挖,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼赃额,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼这揣!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤霎迫,失蹤者是張志新(化名)和其女友劉穎湃窍,沒想到半個(gè)月后誊册,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體波岛,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年险耀,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了弄喘。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡甩牺,死狀恐怖蘑志,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情贬派,我是刑警寧澤急但,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站搞乏,受9級(jí)特大地震影響波桩,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜请敦,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一镐躲、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧侍筛,春花似錦萤皂、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽桥滨。三九已至窝爪,卻和暖如春弛车,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背蒲每。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來泰國打工纷跛, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人邀杏。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓贫奠,卻偏偏與公主長得像,于是被迫代替她去往敵國和親望蜡。 傳聞我的和親對(duì)象是個(gè)殘疾皇子唤崭,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361

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