leetcode-树】从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
思路：
前序遍历顺序是遍历根节点，左子树，右子树，而中序遍历则是左子树，根节点，右子树.
因此这类题目的解题思路是根据前序遍历的第一个元素确定根节点，然后在中顺遍历中找到根节点的位置。在中序遍历的左侧是左子树，右侧是右子树。如上面的例子，首先我们根据前序的第一个节点确定3是根节点，那么在中序遍历结果中找到3，那么中序遍历结果中左侧的序列【9】则是3为根节点的左子树的中序结果，而右侧的序列【15，20，7】则是右子树的中序结果。
确定了左右子树，继续在左子树的中序遍历结果中找到出现在先序遍历结果的元素，因为在先序遍历结果首先出现的一定是子树的根节点。如本题，左子树的中序遍历结果为【9】，只有一个元素，那么一定是9先出现在先序的结果中，因此左子树根节点为9。右子树的中序遍历结果为【15，20，7】，那么首先出现在先序遍历结果【3，9，20，15，7】的元素是20，那么20是右子树的根节点。
因为左子树根节点9在其子树对应的中序结果【9】中没有左侧和右侧的序列，那么9则是一个叶子节点。而右子树根节点20在其对应子树的中序结果【15，20，7】中存在左侧序列【15】和右侧序列【7】，那么【15】对应的则是以20为根节点的左子树的中序结果，而【7】则是以20为根节点的右子树的中序结果。循环递归上面的过程构造子树。
上面的过程是我在数据结构考试中，笔试经常使用的解题思路，反应到程序中需要解决两个重要的问题：
- 先序遍历结果的第一个元素（根节点）在中序遍历结果中的位置如何确定？
- 左子树中序遍历子序列的根节点，即左子树的根节点如何确定？同样，右子树中序遍历子序列的根节点，即右子树的根节点如何确定？
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder ==null || preorder.length==0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
if(preorder.length==1) {
return root;
}
List<Integer> leftIn = new ArrayList<>();
List<Integer> rightIn = new ArrayList<>();
List<Integer> leftPre = new ArrayList<>();
List<Integer> rightPre = new ArrayList<>();
int location =0;
while (inorder[location]!=preorder[0]) {
leftIn.add(inorder[location]);
location++;
}
for(int i=1;i<=location;i++) {
leftPre.add(preorder[i]);
}
for(int i=location+1;i<preorder.length;i++) {
rightIn.add(inorder[i]);
rightPre.add(preorder[i]);
}
int[] leftPres = convertToArray(leftPre);
int[] leftIns = convertToArray(leftIn);
int[] rightPres = convertToArray(rightPre);
int[] rightIns = convertToArray(rightIn);
root.left = buildTree(leftPres, leftIns);
root.right = buildTree(rightPres, rightIns);
return root;
}
private int[] convertToArray(List<Integer> list) {
if(list==null || list.size()==0) {
return null;
}
int[] nums = new int[list.size()];
for(int i=0;i<list.size();i++) {
nums[i]=list.get(i);
}
return nums;
}
}
