題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果怎爵，請重建該二叉樹溉仑。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果都不包含重復(fù)數(shù)字吊说。例如吧兔，輸入前序遍歷序列{1,2,4,7,3,5,6,8} 和中序遍歷序列{4,7,2,1,5,3,8,6}磷仰，則重建的二叉樹為：
1
/ \
2 3
/ / \
4 5 6
\ /
7 8
解題思路:
- 以前序遍歷序列A:{1,2,4,7,3,5,6,8} 和中序遍歷序列B:{4,7,2,1,5,3,8,6} 為例。
- 前序遍歷的第一個數(shù)字"1"為樹的根節(jié)點境蔼。
- "1"將中序遍歷的序列分為兩部分灶平，B1:{4,7,2}和B2:{5,3,8,6}。B1為根節(jié)點左子樹的所有節(jié)點箍土。B2為根節(jié)點右子樹的所有節(jié)點逢享。
- 因為左子樹有三個節(jié)點(B1的數(shù)量)，所以左子樹的前序遍歷為A1:{2,4,7}吴藻。同理右子樹的前序遍歷為A2:{3,5,6,8}瞒爬。
- 此時問題轉(zhuǎn)化為從A1和B1恢復(fù)左子樹，從A2和B2中恢復(fù)右子樹沟堡。
- 遞歸處理即可侧但。
代碼
TreeNode construtTree(int[] preOrder, int[] inOrder) {
if (preOrder == null || inOrder == null) {
return null;
}
if (preOrder.length != inOrder.length) {
return null;
}
return rConstrutTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
}
/**
* @param preOrder 前序遍歷數(shù)組
* @param preS 前序遍歷數(shù)組的開頭index
* @param preE 前序遍歷數(shù)組的末尾index
* @param inOrder 中序遍歷數(shù)組
* @param inS 中序遍歷數(shù)組的開頭index
* @param inE 中序遍歷數(shù)組的末尾index
* @return 返回當(dāng)前序列根節(jié)點
*/
TreeNode rConstrutTree(int[] preOrder, int preS, int preE, int[] inOrder, int inS, int inE){
if (preS > preE || inS > inE) {
return null;
}
TreeNode root = new TreeNode(preOrder[preS]);
int i = inS;
while (inOrder[i] != preOrder[preS]) {
i ++;
}
int nodeCount = i - inS; // 左子樹的節(jié)點數(shù)量
// 遞歸重建左子樹
root.left = rConstrutTree(preOrder, preS + 1, preS + nodeCount, inOrder, inS, inS + nodeCount - 1);
// 遞歸重建右子樹
root.right = rConstrutTree(preOrder, preS + nodeCount + 1, preE, inOrder, inS + nodeCount + 1, inE);
return root;
}
