首页 > 代码库 > [leetcode]重建二叉树(先序和终须) 中序遍和后续
[leetcode]重建二叉树(先序和终须) 中序遍和后续
分割后长度相等,就是参数麻烦,p,先序的起始点, ib,ie 终须的结束和开始。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public TreeNode buildTree(int[] preorder, int[] inorder) {12 return bulid(preorder,inorder, 0, 0,inorder.length-1);// p start of prorder ,ib start of inorder ,ie end of inorder ;13 14 }15 16 /**17 * Definition for binary tree18 * public class TreeNode {19 * int val;20 * TreeNode left;21 * TreeNode right;22 * TreeNode(int x) { val = x; }23 * }24 */25 26 public TreeNode bulid(int[] preorder,int[] inorder,int p,int ib,int ie)27 {28 if(ib>ie) return null;29 int i; //split point30 for(i=ib;i<=ie;i++)31 {32 if(inorder[i]==preorder[p]) break;33 }34 TreeNode root=new TreeNode(preorder[p]);35 root.left= bulid(preorder,inorder,p+1,ib,i-1);36 root.right=bulid(preorder,inorder,p+i-ib+1,i+1,ie);//37 38 39 40 41 return root;42 43 }44 }
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return bulid(inorder,postorder,postorder.length-1,0,inorder.length-1);
}
public TreeNode bulid(int[] in,int[] pos,int p,int ib,int ie)
{
if(ib>ie) return null;
int i;
for(i=ib;i<=ie;i++)
{
if(pos[p]==in[i]) break;
}
TreeNode root=new TreeNode(pos[p]);
root.right=bulid(in,pos,p-1,i+1,ie);
root.left=bulid(in,pos,p-ie+i-1,ib,i-1);
return root;
}
}