题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复数字。例如，输入前序遍历序列{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} 为例。
- 前序遍历的第一个数字"1"为树的根节点。
- "1"将中序遍历的序列分为两部分，B1:{4,7,2}和B2:{5,3,8,6}。B1为根节点左子树的所有节点。B2为根节点右子树的所有节点。
- 因为左子树有三个节点(B1的数量)，所以左子树的前序遍历为A1:{2,4,7}。同理右子树的前序遍历为A2:{3,5,6,8}。
- 此时问题转化为从A1和B1恢复左子树，从A2和B2中恢复右子树。
- 递归处理即可。
代码
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 前序遍历数组
* @param preS 前序遍历数组的开头index
* @param preE 前序遍历数组的末尾index
* @param inOrder 中序遍历数组
* @param inS 中序遍历数组的开头index
* @param inE 中序遍历数组的末尾index
* @return 返回当前序列根节点
*/
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; // 左子树的节点数量
// 递归重建左子树
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;
}
