105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
方法
自己写的方法怎么都跑不通,郁闷,感觉逻辑没有错啊,先放上
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||preorder.length == 0||inorder==null||inorder.length==0){
return null;
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
TreeNode tn = new TreeNode(preorder[pl]);
if(pl == pr && il == ir){
return tn;
}
int index = 0,pl2,pr2,il2,ir2;
for(int i = 0;i <= ir; i++){
if(inorder[i] == preorder[pl]){
index = i;
break;
}
}
il = il;
pl2 = pl+1;
pl = pl + 1;
pr2 = pr;
pr = index;
il2 = index+1;
ir2 = ir;
ir = index-1;
if(pl <= pr && il <= ir)
tn.left = build(preorder,pl,pr,inorder,il,ir);
if(pl2 <= pr2 && il2 <= ir2)
tn.right = build(preorder,pl2,pr2,inorder,il2,ir2);
return tn;
}
}
后面根据之前做剑指offer题目时的修改版本,修改之处为继续判断能否递归以是否在中序下节点左边的长度>0 或者节点右边的长度>0:
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||preorder.length == 0||inorder==null||inorder.length==0){
return null;
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
TreeNode tn = new TreeNode(preorder[pl]);
if(pl == pr && il == ir){
return tn;
}
int index = 0;
for(int i = 0;i <= ir; i++){
if(inorder[i] == preorder[pl]){
index = i;
break;
}
}
int leftLength = index - il;
int rightLength = ir - index;
int leftPreEnd = pl + leftLength;
if(leftLength > 0)
tn.left = build(preorder,pl+1,leftPreEnd,inorder,il,index-1);
if(rightLength > 0)
tn.right = build(preorder,leftPreEnd+1,pr,inorder,index+1,ir);
return tn;
}
}
106. Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
方法
实际上思路与上题类似,注意判断返回条件,以及中序和后序的起止点
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0){
return null;
}
return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
public TreeNode build(int[] inorder, int inl, int inr, int[] postorder, int pl, int pr){
TreeNode root = new TreeNode(postorder[pr]);
if(inl == inr && pl == pr && inorder[inl] == postorder[pl]){
return root;
}
int index = 0;
for(int i = inl; i <= inr; i++){
if(inorder[i] == postorder[pr]){
index = i;
break;
}
}
int leftlength = index - inl;
int rightlength = inr - index;
int prlength = pr - rightlength;
if(leftlength > 0)
root.left = build(inorder,inl,index-1,postorder,pl,pl+leftlength-1);
if(rightlength > 0)
root.right = build(inorder,index+1,inr,postorder,prlength,pr-1);
return root;
}