題目要求
輸入二叉樹的前序遍歷和中序遍歷結(jié)果，重建二叉樹畅涂，假設(shè)前序和中序遍歷中都不含有重復(fù)的數(shù)字， 例如輸入的前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}重建出二叉樹立宜。
題目解析
思路一：
- 分析
對先序與中序進(jìn)行分析
先序：1,2,4,7,3,5,6,8
中序：4,7,2,1,5,3,8,6
通過上面的先序序列臊岸，我們可以確定根節(jié)點(diǎn)的值為1
通過中序序列我們可以知道，4,7,2屬于左子樹5,3,8,6屬于右字樹
同樣的方法我們可以得到左右字樹當(dāng)成一個(gè)整體去逐步構(gòu)造帅戒。
- 代碼段
public static BinaryTreeNode constructCore(int[] preOrder , int[] inOrder) throws Exception {
if(preOrder == null || inOrder == null) {
return null ;
}
if(preOrder.length != inOrder.length) {
throw new Exception("長度不一樣 ， 非法的輸入") ;
}
BinaryTreeNode root = new BinaryTreeNode() ;
for(int i = 0 ; i < preOrder.length ; i++) {
if(inOrder[i] == preOrder[0]) {
root.data = inOrder[i] ;
System.out.println(root.getData());
root.left = constructCore(Arrays.copyOfRange(preOrder, 1, 1+i) ,
Arrays.copyOfRange(inOrder, 0, i)) ;
root.right = constructCore(Arrays.copyOfRange(preOrder, i+1, preOrder.length) ,
Arrays.copyOfRange(inOrder, i, inOrder.length)) ;
}
}
return root ;
}
測試代碼
public static void main(String[] args) {
int[] preOrder = {1,2,4,7,3,5,6,8} ;
int[] inOrder = {4,7,2,1,5,3,8,6} ;
try {
BinaryTreeNode root = constructCore(preOrder, inOrder) ;
} catch (Exception e) {
e.printStackTrace();
}
}
運(yùn)行結(jié)果
無測試結(jié)果
