面試題6：重建二叉樹題目描述：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出圖2.6所示的二叉樹並輸出它的頭結點。二叉 ...

面試題6：重建二叉樹

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出圖2.6所示的二叉樹並輸出它的頭結點。二叉樹結點的定義如下：

class Node{
    int e;
    Node left;
    Node right;
    Node(int x) { e = x; }
}

在這裡插入圖片描述

這道題主要測試你對二叉樹性質的瞭解，非常有代表性，不過在這之前，我們先把二叉樹的基本性質捋一遍。

二叉樹的基本性質

（1）關於樹

樹是一種數據結構，它是由n（n>=1）個有限結點組成一個具有層次關係的集合。

在這裡插入圖片描述

樹的基本術語有：

每個結點有零個或多個子結點
沒有父節點的結點稱為根節點
每一個非根結點有且只有一個父節點
除了根結點外，每個子結點可以分為多個不相交的子樹。
若一個結點有子樹，那麼該結點稱為子樹根的“雙親”，子樹的根稱為該結點的“孩子”。有相同雙親的結點互為“兄弟”。
一個結點的所有子樹上的任何結點都是該結點的後裔。從根結點到某個結點的路徑上的所有結點都是該結點的祖先。
結點的度：結點擁有的子樹的數目
葉子結點：度為0的結點
分支結點：度不為0的結點
樹的度：樹中結點的最大的度
層次：根結點的層次為1，其餘結點的層次等於該結點的雙親結點的層次加1
樹的高度：樹中結點的最大層次
森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。

“樹”是電腦科學中非常重要的一部分內容，它的變形和應用非常之多。比如說，在做通訊錄的時候，Android 工程師往往喜歡用字典樹來存取數據，對於Java後端，有的時候我們處理的數據的時候也需要進行區間的查詢，比如說去年你的博客在什麼時間段關註你的人增長最快啊，一天中自己的博文閱讀量最高的時間段啊，可以採用線段樹來實現。在JDK1.8的HashMap的結構中，當元素超過8個的時候，會轉為紅黑樹等等。

不過對於Java開發而言，二叉樹是基礎也是接觸較多的一種結構。

（2）關於二叉樹

二叉樹是每個結點最多有兩個子樹的樹結構。它有五種基本形態：

1)空樹;

2)只有根的樹,即單結點;

3)有根且有一個左子樹;

4)有根且有一個右子樹;

5)有根且有一個左子樹,有一個右子樹。

二叉樹的性質有：

二叉樹第i層上的結點數目最多為2i-1(i>=1)
深度為k的二叉樹至多有2k-1個結點（k>=1）
包含n個結點的二叉樹的高度至少為(log2n)+1
在任意一棵二叉樹中，若葉子結點的個數為n0，度為2的結點數為n2，則n0=n2+1

第四條的證明：因為二叉樹中所有結點的度數均不大於2，設n0表示度為0的結點個數，n1表示度為1的結點個數，n2表示度為2的結點個數。
三類結點加起來為總結點個數，於是便可得到：n=n0+n1+n2 (公式1)
由度之間的關係可得第二個等式：n=n0*0+n1*1+n2*2+1 即n=n1+2n2+1 (公式2)
將（公式1）（公式2）組合在一起可得到n0=n2+1

瞭解這第四條性質就差不多了。如果想進一步學習二叉樹的性質，不妨去找本《離散數學》？

對二叉樹遍歷的理解

以這棵樹為例：

在這裡插入圖片描述

前序遍歷：根結點 —> 左子樹 —> 右子樹（先遍歷根節點，然後左右）

    //前序遍歷以node為根
    public void preOrder(Node node) {
        //終止條件
        if(node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

這棵樹的前序遍歷為：FCADBEHGM

中序遍歷：左子樹—> 根結點 —> 右子樹（在中間遍歷根節點）

    //中序以node為根的
    public void inOrder(Node node) {
        //終止條件
        if(node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

這棵樹的中序遍歷為：ACBDFHEMG

後序遍歷：左子樹 —> 右子樹 —> 根結點（最後遍歷根節點）

        //中序以node為根
        public void postOrder(Node node) {
            //終止條件
            if(node == null) {
                return;
            }
    
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }

這棵樹的後序遍歷為：ABDCHMGEF

層序遍歷：

    //層序遍歷
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while( !q.isEmpty() ) {
            Node cur = q.remove();
            System.out.println(cur.e);
            
            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.right);  //後出
        }
    }

這棵樹層序遍歷為：FCEADHGBM

所謂的前序、中序、後序，就是對根節點而言的，左右的遍歷順序不變，前序就是根節點最先遍歷，然後左右；中序就是把根節點放在中間遍歷；後序則是把根節點放在最後遍歷。

中序遍歷能夠幫助我們很好地確定根節點的位置，這個就有點可怕了，實際面試的時候，不單單會有給出前序遍歷和中序遍歷的結果讓你重建二叉樹，還有給出後序遍歷和中序遍歷結果或者 層序遍歷和中序遍歷的結果重建二叉樹、

其他的遍歷組合均不能還原出二叉樹的形狀，因為無法確認其左右孩子。例如，前序為AB，後序為AB，則無法確認出，B節點是A節點的左孩子還是右孩子，因此無法還原。

題解

思路：通過前序遍歷獲得根節點的位置，利用根節點將中序序列分為左子樹和右子樹，然後不斷的遞歸劃分即可。

代碼中有解釋。

  private Node buildTree(int[] pre, int preBegin, int preEnd, int[] mid, int midBegin, int midEnd) {
        // 前序遍歷確第一個元素為根節點
        Node root = new Node(pre[preBegin]);
        // 用於標記中序遍歷結果中根節點的位置
        int midRootLocation= 0;
        for (int i = midBegin; i <= midEnd; i++) {
            if (mid[i] == pre[preBegin]) {  
                midRootLocation= i;
                break;
            }
        }

        if ( midRootLocation - midBegin >= 1 ) {
            // 遞歸得到左子樹
            
            // 中序遍歷：左子樹—> 根結點 —> 右子樹（在中間遍歷根節點）
            // midRootLocation標記了中序遍歷結果中根節點的位置，這個位置兩端對應根節點左子樹和右子樹
            // midRootLocation- midBegin 表示該根節點左邊的節點的數量
            
            // 前序遍歷：根結點 —> 左子樹 —> 右子樹（先遍歷根節點，然後左右）
            // preBegin 標記了前序遍歷結果中根節點的位置
            // preBegin + 1 表示該根節點左子樹起始位置
            // preBegin + (midRootLocation- midBegin) 表示給根節點左子樹結束的位置
            Node left = buildTree(pre, preBegin + 1, preBegin + (midRootLocation- midBegin),
                    mid, midBegin, midRootLocation - 1);
            root.left = left;
        }


        if ( midEnd - midRootLocation >= 1 ) {
            // 遞歸得到右子樹
            // 原理和上面相同
            Node right = buildTree(pre, preEnd - (midEnd - midRootLocation) + 1, preEnd,
                    mid, midRootLocation+ 1, midEnd);
            root.right = right;
        }

        return root;
    }

舉一反三

（1）給出後序遍歷和中序遍歷的結果重建二叉樹

思路：通過後序獲取根節點的位置，然後在中序中劃分左子樹和右子樹，然後遞歸劃分即可。

形式與上面給出前序遍歷和中序遍歷的結果重建二叉樹相同

    private Node buildTree(int[] mid, int midBegin, int midEnd, int[] end, int endBegin, int endEnd) {
        
        Node root = new Node(end[endEnd]);
        int midRootLocation = 0;
        for (int i = midEnd; i >= midBegin; i--) {
            if (mid[i] == end[endEnd]) {
                midRootLocation = i;
                break;
            }
        }
        
        //還原左子樹
        if (midRootLocation - midBegin >= 1 ) {
            Node left = buildTree(mid, midBegin, midRootLocation - 1, end, endBegin, endBegin + (midRootLocation - midBegin) - 1);
            root.left = left;
        }

        //還原右子樹
        if (midEnd - midRootLocation >=  1 ) {
            Node right = buildTree(mid, midRootLocation + 1, midEnd, end, endEnd - (midEnd - midRootLocation), endEnd - 1);
            root.right = right;
        }
        
        return root;
    }

（2）給出層序遍歷和中序遍歷結果重建二叉樹

思路：

（1）根據層序遍歷獲取根節點的位置

（2）根據（1）將中序劃分為左子樹和右子樹

（3）根據（2）劃分出的左子樹和右子樹分別在層序遍歷中獲取其對應的層序順序

（4）然後遞歸調用劃分。

  private Node buildTree(int[] mid, int[] level, int midBegin, int midEnd) {

        // 層序遍歷的第一個結果是 根節點
        Node root = new Node(level[0]);
        // 用於標記中序遍歷的根節點
        int midLocation = -1;
        for (int i = midBegin; i <= midEnd; i++) {
            if (mid[i] == level[0]) {
                midLocation = i;
                break;
            }
        }

        if (level.length >= 2) {
            if (isLeft(mid, level[0], level[1])) {
                Node left = buildTree(mid, getLevelArray(mid, midBegin, midLocation - 1, level), midBegin, midLocation - 1);
                root.left = left;
                if (level.length >= 3 && !isLeft(mid, level[0], level[2])) {
                    Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
                    root.right = right;
                }
            } else {
                Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
                root.right = right;
            }
        }
        return root;
    }


    // 功能 ： 判斷元素是根節點的左子樹節點還是右子樹節點
    // 參數 ： target為根節點 isLeft在中序遍歷結果中判斷children是根節點的左子樹還是右子樹
    // 返回值 : 如果為左子樹節點則為true 否則為false
    private boolean isLeft(int[] array, int target, int children) {
        boolean findC = false;

        for (int temp : array) {
            if (temp == children) {
                findC = true;
            } else if (temp == target) {
                return findC;
            }
        }
        return false;
    }


    // 功能： 將中序序列中midBegin與midEnd的元素依次從level中提取出來，保持level中的元素順序不變
    private int[] getLevelArray(int[] mid, int midBegin, int midEnd, int[] level) {
        int[] result = new int[midEnd - midBegin + 1];
        int curLocation = 0;
        for (int i = 0; i < level.length; i++) {
            if (contains(mid, level[i], midBegin, midEnd)) {
                result[curLocation++] = level[i];
            }
        }
        return result;
    }

    // 如果array的begin和end位置之間（包括begin和end）含有target,則返回true。
    private boolean contains(int[] array, int target, int begin, int end) {
        for (int i = begin; i <= end; i++) {
            if (array[i] == target) {
                return true;
            }
        }
        return false;
    }

劍指Offer對答如流系列 - 重建二叉樹

面試題6：重建二叉樹

二叉樹的基本性質

對二叉樹遍歷的理解

題解

舉一反三