在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

劍指offer之重建二叉樹

1 問題

重建二叉樹：給定二叉樹的先序遍歷（根左右）和中序（左中右）遍歷結(jié)果，建立這棵二叉樹。輸入保證二叉樹無重復(fù)結(jié)點

以先序{1, 2, 4, 7, 3, 5, 6, 8}和中序{4, 7, 2, 1, 5, 3, 8, 6}為例

 
2 分析

先序遍歷的特點，我們知道{1, 2, 4, 7, 3, 5, 6, 8}第一個元素1就是樹的根節(jié)點，然后中序遍歷{4, 7, 2, 1, 5, 3, 8, 6}的根節(jié)點在中間，因為我們從先序遍歷里面得知1就是根節(jié)點，所以在中序遍歷{4, 7, 2, 1, 5, 3, 8, 6}中，在中序遍歷數(shù)組1的左邊元素都是根節(jié)點左子樹{4, 7, 2,}，這里是3個元素，所以在先序數(shù)組里面根節(jié)點1的后面3個元素也是左子樹{2,4,7}，也是根節(jié)點的左子樹，在中序遍歷1的右邊邊元素都是{5, 3, 8, 6}都是根節(jié)點的右子樹，然后我們在先序數(shù)組里面根節(jié)點1的后面第3個元素的后面到尾巴，也就是{3,5,6,8}也就是根節(jié)點的右子樹。然后我們再把問題分解成構(gòu)建左子樹{2,4,7}和構(gòu)建右子樹{3,5,6,8}，以此遞歸處理。

我們構(gòu)建左子樹

再構(gòu)建右子樹

 
3 代碼實現(xiàn)

    import java.io.*;
     
    class Tree
    {
        public int value;
        public Tree left;
        public Tree right;
        
        public Tree(int value)
        {
            this.value = value;
            this.left = null;
            this.right = null;
        }
        
        /**
         *前序遍歷
         */
        public void printTree(Tree node)
        {
            if (null == node)
                return;
            System.out.println("value is " + node.value);
            printTree(node.left);
            printTree(node.right);
        }
        
        /*
         *得到樹的根節(jié)點
         */
        public Tree getTree(int[] preDatas, int[] inDatas)
        {
            if (null == preDatas || null == inDatas)
            {
                System.out.println("preDatas is null or inDatas is null");
                return null;
            }
            Tree tree = buildTree(preDatas, 0, preDatas.length - 1, inDatas, 0, inDatas.length - 1);
            return tree;
        }
        
        /*
         *構(gòu)建樹的左右子結(jié)構(gòu)
         */
        public Tree buildTree(int[] preDatas, int preStart, int preEnd, int[] inDatas, int inStart, int inEnd)
        {
            if (null == preDatas || null == inDatas)
            {
                System.out.println("preDatas is null or inDatas is null");
                return null;
            }
            System.out.println("preStart is:" + preStart + " preEnd is" + preEnd + " inStart is " + inStart + " inEnd is" + inEnd);
            //這里就是進(jìn)行如果樹的左子節(jié)點和右子節(jié)點是否為空進(jìn)行設(shè)置
            if (preStart > preEnd || inStart > inEnd)
            {
                return null;
            }
            Tree tree = new Tree(preDatas[preStart]);
            for (int i = inStart; i <= inEnd; ++i)
            {   
                System.out.println("preDatas[preStart] is " + preDatas[preStart]);
                if (preDatas[preStart] == inDatas[i])
                {
                    tree.left = buildTree(preDatas, preStart + 1, preStart + i - inStart, inDatas, inStart, i - 1);
                    tree.right = buildTree(preDatas, preStart + i - inStart + 1, preEnd, inDatas, i + 1, inEnd);
                    break;
                }
            }
            return tree;
        }
    }
     
    class test  
    {
        public static void main (String[] args) throws java.lang.Exception
        {
            int[] preDatas = {1, 2, 4, 7, 3, 5, 6, 8};
                int[] inDatas = {4, 7, 2, 1, 5, 3, 8, 6};
                Tree test =  new Tree(0);
                Tree tree = test.getTree(preDatas, inDatas);
                if (tree == null)
                {
                    System.out.println("tree is null");
                    return;
                }
                //我們進(jìn)行前序打印樹        
                test.printTree(tree);
                
        }
    }

 
4 運行結(jié)果

    preStart is:0 preEnd is7 inStart is 0 inEnd is7
    preDatas[preStart] is 1
    preDatas[preStart] is 1
    preDatas[preStart] is 1
    preDatas[preStart] is 1
    preStart is:1 preEnd is3 inStart is 0 inEnd is2
    preDatas[preStart] is 2
    preDatas[preStart] is 2
    preDatas[preStart] is 2
    preStart is:2 preEnd is3 inStart is 0 inEnd is1
    preDatas[preStart] is 4
    preStart is:3 preEnd is2 inStart is 0 inEnd is-1
    preStart is:3 preEnd is3 inStart is 1 inEnd is1
    preDatas[preStart] is 7
    preStart is:4 preEnd is3 inStart is 1 inEnd is0
    preStart is:4 preEnd is3 inStart is 2 inEnd is1
    preStart is:4 preEnd is3 inStart is 3 inEnd is2
    preStart is:4 preEnd is7 inStart is 4 inEnd is7
    preDatas[preStart] is 3
    preDatas[preStart] is 3
    preStart is:5 preEnd is5 inStart is 4 inEnd is4
    preDatas[preStart] is 5
    preStart is:6 preEnd is5 inStart is 4 inEnd is3
    preStart is:6 preEnd is5 inStart is 5 inEnd is4
    preStart is:6 preEnd is7 inStart is 6 inEnd is7
    preDatas[preStart] is 6
    preDatas[preStart] is 6
    preStart is:7 preEnd is7 inStart is 6 inEnd is6
    preDatas[preStart] is 8
    preStart is:8 preEnd is7 inStart is 6 inEnd is5
    preStart is:8 preEnd is7 inStart is 7 inEnd is6
    preStart is:8 preEnd is7 inStart is 8 inEnd is7
    value is 1
    value is 2
    value is 4
    value is 7
    value is 3
    value is 5
    value is 6
    value is 8
    

 
5 總結(jié)

中途遇到這個一個錯誤

error: <identifier> expected

是我在手寫函數(shù)的時候參數(shù)前面忘記了定義類型，所以報這個錯誤。

我們這里用了4個指針，分別是先序的起尾指針和中序的起尾指針，然后我們不斷更新4個指針指針的位置，然后當(dāng)先序的起指針大于尾指針的時候或者中序的起指針大于尾指針的時候我們就構(gòu)建空指針，就這樣遞歸處理就行。
 

作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)