Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
/**
* 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) {
if(inorder==null || postorder==null || inorder.length!=postorder.length || inorder.length==0) {
return null;
}
TreeNode root = new TreeNode(inorder[inorder.length-1]);
return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
private int find(int[] inorder, int inS, int inE, int root) {
for(int i=inS;i<=inE;i++) {
if(inorder[i]==root) {
return i;
}
}
return -1;
}
private TreeNode build(int[] inorder, int inS, int inE, int[] postorder, int poS, int poE) {
if(inS>inE || poS>poE) {
return null;
}
TreeNode root = new TreeNode(postorder[poE]);
int mid = find(inorder, inS, inE, postorder[poE]);
int leftSize = mid - inS;
//int rightSize = inE - inS - leftSize;
root.left = build(inorder, inS, mid -1, postorder, poS, poS+leftSize-1);
root.right = build(inorder, mid+1, inE, postorder, poS+leftSize, poE-1);
return root;
}
}
没有评论:
发表评论