題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果庵芭，請(qǐng)重建出該二叉樹喜喂。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}井厌，則重建二叉樹并返回秒赤。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
我的解法：
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return fun(pre, in, 0, pre.length,0 ,in.length -1 );
}
private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){
if(inLeftIndex > inRightIndex || preLeftIndex > preRightIndex){
return null;
}
TreeNode root = new TreeNode(pre[preLeftIndex]);
for(int i = inLeftIndex; i <= inRightIndex; i++){
if(in[i] == pre[preLeftIndex]){
root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );
root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);
break;
}
}
return root;
}
}
思路：
二叉樹的前序遍歷和中序遍歷
- 前序遍歷：先訪問當(dāng)前節(jié)點(diǎn)，然后以前序訪問左子樹痹愚，右子樹富岳。
- 中序遍歷：先以中序遍歷左子樹，接著訪問當(dāng)前節(jié)點(diǎn)拯腮，然后以中序遍歷右子樹窖式。
所以前序遍歷的特點(diǎn)為：前序遍歷的每一個(gè)節(jié)點(diǎn)都是當(dāng)前子樹的根節(jié)點(diǎn)，同時(shí)动壤，以中序遍歷中該節(jié)點(diǎn)為邊界萝喘，可以把中序遍歷的結(jié)果分為左子樹和右子樹
- 前序遍歷序列{*1,2,4,7,3,5,6,8}
- 中序遍歷序列{4,7,2,*1,5,3,8,6}
前序遍歷的第一個(gè)節(jié)點(diǎn)將中序遍歷的結(jié)果分成了{(lán)4,7,2}和{5,3,8,6}兩部分，他就是以1為根的左右兩個(gè)子樹的全部節(jié)點(diǎn)
然后接著將其子樹按照上述方法進(jìn)行拆分琼懊，就可以獲得原始的樹結(jié)構(gòu)了阁簸。
注：此種解法要保證在樹中無重復(fù)節(jié)點(diǎn)
幾個(gè)需要注意的點(diǎn)：
- 邊界檢查
- 如過要想復(fù)原一顆二叉樹，需要知道他的前/后序遍歷+中序遍歷 因?yàn)榍靶蚝秃笮虮举|(zhì)上是一樣的肩碟，只有應(yīng)用兩種性質(zhì)不一致的方式才能復(fù)原二叉樹强窖。
