自己写的,思路是,对于一个节点,它的前序遍历,这个节点之后先跟着他左边的结点,再跟着它右边的结点。对于中序遍历,这个节点左面的,是他的左面的结点,右面的,是他右面的结点。
因此,按照前序的顺序,从前往后,并按照其所在中序的位置,找到前序中,以这个节点为根节点,分开的左右部分,递归建立。
/**
* 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.length==0){
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int index=-1;
for(int count = 0;count<inorder.length;count++){
if(inorder[count]==root.val){
index = count;
}
}
root.left = findNode(preorder,1,index,inorder,0,index-1);
root.right = findNode(preorder,index+1,preorder.length-1,inorder,index+1,inorder.length-1);
return root;
}
public TreeNode findNode(int[] preorder, int pre_s,int pre_e,int[] inorder,int in_s,int in_e){
if(pre_s>pre_e||in_s>in_e){
return null;
}else if(pre_s==pre_e&&in_s==in_e){
return new TreeNode(preorder[pre_s]);
}
TreeNode root = new TreeNode(preorder[pre_s]);
int index=-1;
for(int count = in_s;count<=in_e;count++){
if(inorder[count]==root.val){
index = count;
}
}
root.left = findNode(preorder,pre_s+1,pre_s+index-in_s,inorder,in_s,index-1);
root.right = findNode(preorder,pre_s+index-in_s+1,pre_e,inorder,index+1,in_e);
return root;
}
}