劍指Offer面試題6(Java版):重建二叉樹

題目:輸入某二叉樹的前序遍歷和中序遍歷的結果,請重新構造出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中不包含重複的數字。例如輸入的前序遍歷序列為{1,2,4,7,3,5,6,8}和中序遍歷為{4,7,2,1,5,3,6,8},則重建出二叉樹並輸出它的頭結點。

在二叉樹的前序遍歷序列中,第一個數字總是樹的根節點的值。但在中序遍歷中,根節點的值在序列的中間,左子樹的結點的值位於根節點的值的左邊,而右子樹的結點的值位於根節點的右邊。因此我們需要掃描中序遍歷序列,才能找到根節點的值。

如圖所示,前序遍歷序列的第一個數字1就是根節點的值。掃描中序遍歷序列,就能確定根節點的值的位置。根據中序遍歷的特點,在根節點的值1前面3個數字都是左子樹結點的值,位於1後面的數字都是右子樹結點的值。

由於中序遍歷序列中,有3個數字是左子樹結點的值,因此左子樹總共有3個左子結點。同樣,在前序遍歷的序列中,根節點後面的3個數字就是3個左子樹結點的值,再後面的所有數字都是右子樹結點的值。這樣我們就在前序遍歷和中序遍歷兩個序列中,分別找到了左右子樹對應的子序列。

既然我們已經分別找到了左、右子樹的前序遍歷序列和中序遍歷序列,我們可以用同樣的方法分別去構建左右子樹。也就是說,接下來的事情可以用遞迴的方法去完成。

我們使用Java語言來實現上面的程式碼:

首先構建二叉樹程式碼:

package utils;
public class BinaryTreeNode {
public int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
public BinaryTreeNode(){
}
public BinaryTreeNode(int value){
this.value = value ;
this.leftNode = null;
this.rightNode = null;
}
}

重建二叉樹程式碼:

package swordForOffer;
/**
* @author JInShuangQi
*
* 2015年7月25日
*/
import utils.BinaryTreeNode;
public class E06ConstructBinaryTree {
/**
* 
* @param preOrder 前序遍歷陣列
* @param inOrder 中序遍歷陣列
* @param length 陣列長度
* @return 根結點
*/
public static BinaryTreeNode Construct(int[] preOrder, int[] inOrder,int length){
if (preOrder == null || inOrder == null || length <= 0) {
return null;
}
try {
return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);
} catch (InvalidPutException e) {
e.printStackTrace();
return null;
}
}
/**
* 
* @param PreOrder
*            前序遍歷序列
* @param startPreIndex
*            前序序列開始位置
* @param endPreIndex
*            前序序列結束位置
* @param InOrder
*            中序遍歷序列
* @param startInIndex
*            中序序列開始位置
* @param endInIndex
*            中序序列結束位置
* @return 根結點
* @throws InvalidPutException
*/
public static BinaryTreeNode ConstructCore(int[] preOrder,int startPreIndex, int endPreIndex, 
int[] inOrder,int startInIndex, int endInIndex) throws InvalidPutException {
int rootValue = preOrder[startPreIndex];
System.out.println("rootValue = "   rootValue);
BinaryTreeNode root = new BinaryTreeNode(rootValue);
// 只有一個元素
if (startPreIndex == endPreIndex) {
if (startInIndex == endInIndex
&& preOrder[startPreIndex] == inOrder[startInIndex]) {
System.out.println("only one element");
return root;
} else {
throw new InvalidPutException();
}
}
// 在中序遍歷中找到根結點的索引
int rootInIndex = startInIndex;
while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
rootInIndex;
}
if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
throw new InvalidPutException();
}
int leftLength = rootInIndex - startInIndex;
int leftPreOrderEndIndex = startPreIndex   leftLength;
if (leftLength > 0) {
// 構建左子樹
root.leftNode = ConstructCore(preOrder, startPreIndex   1,
leftPreOrderEndIndex, inOrder, startInIndex,
rootInIndex - 1);
}
if (leftLength < endPreIndex - startPreIndex) {
// 右子樹有元素,構建右子樹
root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex   1,
endPreIndex, inOrder, rootInIndex   1, endInIndex);
}
return root;
}
static class InvalidPutException extends Exception {
private static final long serialVersionUID = 1L;
}
public static void printPreOrder(BinaryTreeNode root) {
if (root == null) {
return;
} else {
System.out.print(root.value   " ");
}
if (root.leftNode != null) {
printPreOrder(root.leftNode);
}
if (root.rightNode != null) {
printPreOrder(root.rightNode);
}
}
public static void main(String[] args) throws Exception{
E06ConstructBinaryTree test=new E06ConstructBinaryTree();
int[] preOrder={1,2,4,7,3,5,6,8};
int[] inOrder={4,7,2,1,5,3,8,6};
printPreOrder(Construct(preOrder, inOrder, preOrder.length));
}
}

在函式ConstructCore中,我們先根據先序遍歷的第一個數字建立根節點,接下來在中序遍歷中找到根節點的位置,這樣就能確定左右子樹節點的數量。在前序遍歷和中序遍歷的序列中劃分左右子樹節點的值之後,我們就可以遞迴呼叫函式ConstructCore,去分別構建它的左右子樹。