問題：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如尿赚，輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}。
先上代碼沛婴。
/**
* 重建二叉樹
*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return core(pre, in, 0,pre.length - 1, 0, in.length - 1);
}
public TreeNode core(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
// 根節(jié)點(前序遍歷的第一個節(jié)點)
int rootVal = pre[preStart];
TreeNode root = new TreeNode(rootVal);
// 找到根節(jié)點在中序遍歷數(shù)組中的位置
int rootIndexIn = inStart;
for(;rootIndexIn <= inEnd; rootIndexIn++){
if(in[rootIndexIn] == rootVal)
break;
}
// 計算左子樹的長度
int leftLen = rootIndexIn - inStart;
// 計算右子樹的長度
int rightLen = inEnd - rootIndexIn;
if(leftLen > 0){
// 存在左子樹
// 找到左子樹的中序遍歷數(shù)組
int leftInStart = inStart;
int leftInEnd = leftInStart + leftLen - 1;
// 找到左子樹的前序遍歷數(shù)組
int leftPreStart = preStart + 1;
int leftPreEnd = leftPreStart + leftLen - 1;
// 構(gòu)建左子樹
root.left = core(pre,in,leftPreStart, leftPreEnd, leftInStart, leftInEnd);
}
if(rightLen > 0){
// 存在右子樹
// 找到右子樹的中序遍歷數(shù)組
int rightInStart = rootIndexIn + 1;
int rightInEnd = rightInStart + rightLen - 1;
// 找到右子樹的前序遍歷數(shù)組
int rightPreStart = preEnd - rightLen + 1;
int rightPreEnd = preEnd;
// 構(gòu)建右子樹
root.right = core(pre, in, rightPreStart, rightPreEnd, rightInStart, rightInEnd);
}
return root;
}
關(guān)于樹的問題很多都可以使用遞歸的方式解決吼畏，只要將一般化的處理過程想清楚督赤，再把返回條件搞好嘁灯，基本就可以。本題已知二叉樹的前序遍歷和中序遍歷結(jié)果躲舌，找出根節(jié)點的值丑婿，然后再根據(jù)這個值找出左子樹和右子樹對應(yīng)的前序和中序遍歷結(jié)果，就可以進行遞歸編程了没卸。此題比較麻煩的子樹數(shù)組的界限問題羹奉，處理好這個問題，遞歸也就不會出錯了约计。
詳細的解題流程在注釋里已經(jīng)比較清楚诀拭，不再贅述。
