重構(gòu)二叉樹

原文鏈接:http://blog.csdn.net/qq_22329521/article/details/52948072
二叉樹的遍歷常見方式

enter image description here

  • 前序遍歷,先訪問跟節(jié)點(diǎn),在訪問子結(jié)點(diǎn),最后訪問右子結(jié)點(diǎn)順序是abdefgc
  • 中序遍歷,先訪問左子結(jié)點(diǎn),再訪問根結(jié)點(diǎn)宪睹,最后訪問右子結(jié)點(diǎn)debgfac
  • 后序遍歷,先訪問左子結(jié)點(diǎn)蚕钦,在訪問右子結(jié)點(diǎn)亭病,最后訪問更結(jié)點(diǎn)edgfbca
  • 寬度優(yōu)先遍歷,先訪問樹的第一層結(jié)點(diǎn)嘶居,再訪問樹的第二層結(jié)點(diǎn)罪帖,一致到訪問到最下面一層結(jié)點(diǎn),同一層結(jié)點(diǎn)邮屁,從左到右一次遍歷abcdfeg

重構(gòu)二叉樹

輸入二叉樹的前序遍歷和中序遍歷都不含重復(fù)數(shù)字整袁,重建該二叉樹
思路:已知前序找根結(jié)點(diǎn),然后判斷跟結(jié)點(diǎn)在中序輸出中的位置佑吝,根節(jié)點(diǎn)左邊的就是左子樹坐昙,右邊就是右子樹,遞歸查找

 public static void test4() {
        int[] frontOrder = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeNode root = BinaryTree(frontOrder, inOrder);
        printPostOrder(root);
    }

    public static void printPostOrder(BinaryTreeNode root) {
        if (root != null) {
            printPostOrder(root.getLeft());
            printPostOrder(root.getRight());
            System.out.println(root.getValue());
        }
    }

    public static BinaryTreeNode BinaryTree(int[] frontOrder, int[] inOrder) {
        //根據(jù)前序結(jié)點(diǎn)獲取當(dāng)前的跟結(jié)點(diǎn)
        BinaryTreeNode root = new BinaryTreeNode(frontOrder[0]);
        root.setLeft(null);
        root.setRight(null);
        int leftLength = 0;
        //從中序結(jié)點(diǎn)中獲取前序結(jié)點(diǎn)這個(gè)數(shù)所在的位置芋忿,因?yàn)橹行蚪Y(jié)點(diǎn)中左側(cè)是左字?jǐn)?shù)炸客,右側(cè)是右字?jǐn)?shù)
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == root.getValue()) {
                break;
            } else {
                leftLength++;
            }
        }
        //獲取右子樹的個(gè)數(shù)
        int rightLength = inOrder.length - leftLength - 1;
        if (leftLength > 0) {
            //再次初始化左側(cè)的左子樹
            int[] leftFrontOrder = new int[leftLength];
            int[] leftInorder = new int[leftLength];
            for (int j = 0; j < leftLength; j++) {
                //因?yàn)榈谝粋€(gè)被取走了
                leftFrontOrder[j] = frontOrder[j + 1];
                leftInorder[j] = inOrder[j];
            }
            BinaryTreeNode leftRoot = BinaryTree(leftFrontOrder, leftInorder);
            root.setLeft(leftRoot);
        }
        //再次初始化右側(cè)的右子樹
        if (rightLength > 0) {
            int[] rightFrontOrder = new int[rightLength];
            int[] rightInorder = new int[rightLength];
            for (int k = 0; k < rightLength; k++) {
                rightFrontOrder[k] = frontOrder[k + 1 + leftLength];
                rightInorder[k] = inOrder[k + 1 + leftLength];
            }
            BinaryTreeNode rightRoot = BinaryTree(rightFrontOrder, rightInorder);
            root.setRight(rightRoot);
        }
        return root;
    }

public class BinaryTreeNode {
    private int value;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    public BinaryTreeNode(int value){
        this.value = value;
    }
    public BinaryTreeNode(int value,BinaryTreeNode left,BinaryTreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public int getValue( ){
        return this.value;
    }
    public void setValue(BinaryTreeNode node){
        this.value = value;
    }
    public void  setLeft(BinaryTreeNode node){
        this.left = node;
    }
    public void  setRight(BinaryTreeNode node){
        this.right = node;
    }
    public BinaryTreeNode getLeft( ){
        return this.left;
    }
    public BinaryTreeNode getRight( ){
        return this.right;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市盗飒,隨后出現(xiàn)的幾起案子嚷量,更是在濱河造成了極大的恐慌,老刑警劉巖逆趣,帶你破解...
    沈念sama閱讀 217,734評(píng)論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異嗜历,居然都是意外死亡宣渗,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,931評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門梨州,熙熙樓的掌柜王于貴愁眉苦臉地迎上來痕囱,“玉大人,你說我怎么就攤上這事暴匠“盎郑” “怎么了?”我有些...
    開封第一講書人閱讀 164,133評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長帮掉。 經(jīng)常有香客問我弦悉,道長,這世上最難降的妖魔是什么蟆炊? 我笑而不...
    開封第一講書人閱讀 58,532評(píng)論 1 293
  • 正文 為了忘掉前任稽莉,我火速辦了婚禮,結(jié)果婚禮上涩搓,老公的妹妹穿的比我還像新娘污秆。我一直安慰自己,他們只是感情好昧甘,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,585評(píng)論 6 392
  • 文/花漫 我一把揭開白布良拼。 她就那樣靜靜地躺著,像睡著了一般充边。 火紅的嫁衣襯著肌膚如雪将饺。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,462評(píng)論 1 302
  • 那天痛黎,我揣著相機(jī)與錄音予弧,去河邊找鬼。 笑死湖饱,一個(gè)胖子當(dāng)著我的面吹牛掖蛤,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播井厌,決...
    沈念sama閱讀 40,262評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼蚓庭,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了仅仆?” 一聲冷哼從身側(cè)響起器赞,我...
    開封第一講書人閱讀 39,153評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎墓拜,沒想到半個(gè)月后港柜,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,587評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡咳榜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,792評(píng)論 3 336
  • 正文 我和宋清朗相戀三年夏醉,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片涌韩。...
    茶點(diǎn)故事閱讀 39,919評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡畔柔,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出臣樱,到底是詐尸還是另有隱情靶擦,我是刑警寧澤腮考,帶...
    沈念sama閱讀 35,635評(píng)論 5 345
  • 正文 年R本政府宣布,位于F島的核電站玄捕,受9級(jí)特大地震影響踩蔚,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜桩盲,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,237評(píng)論 3 329
  • 文/蒙蒙 一寂纪、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧赌结,春花似錦捞蛋、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,855評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至量承,卻和暖如春搬设,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背撕捍。 一陣腳步聲響...
    開封第一講書人閱讀 32,983評(píng)論 1 269
  • 我被黑心中介騙來泰國打工拿穴, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人忧风。 一個(gè)月前我還...
    沈念sama閱讀 48,048評(píng)論 3 370
  • 正文 我出身青樓默色,卻偏偏與公主長得像,于是被迫代替她去往敵國和親狮腿。 傳聞我的和親對(duì)象是個(gè)殘疾皇子腿宰,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,864評(píng)論 2 354

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

  • 數(shù)據(jù)結(jié)構(gòu)和算法--二叉樹的實(shí)現(xiàn) 幾種二叉樹 1、二叉樹 和普通的樹相比缘厢,二叉樹有如下特點(diǎn): 每個(gè)結(jié)點(diǎn)最多只有兩棵子...
    sunhaiyu閱讀 6,461評(píng)論 0 14
  • 四贴硫、樹與二叉樹 1. 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 二叉樹的順序存儲(chǔ)就是用數(shù)組存儲(chǔ)二叉樹椿每。二叉樹的每個(gè)結(jié)點(diǎn)在順序存儲(chǔ)中都有...
    MinoyJet閱讀 1,528評(píng)論 0 7
  • 樹和二叉樹 1、樹的定義 樹(Tree)是由一個(gè) 或 多個(gè)結(jié)點(diǎn) 組成的有限集合T夜畴,且滿足: ①有且僅有一個(gè)稱為根的...
    利伊奧克兒閱讀 1,367評(píng)論 0 1
  • 1.樹(Tree): 樹是 n(n>=0) 個(gè)結(jié)點(diǎn)的有限集拖刃。當(dāng) n=0 時(shí)稱為空樹。在任意一顆非空樹中:有且僅有一...
    ql2012jz閱讀 1,006評(píng)論 0 3
  • 幾年前央碟,美國六歲孩子最感興趣的是一群叫作“金剛戰(zhàn)士”(Mighty Mortphin Power Rangers)...
    Baron_0065閱讀 162評(píng)論 0 0