Note:
You may assume that duplicates do not exist in the tree.
Solution:
/**
* 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 buildTree(inorder, postorder, inorder.length, 0, 0);
}
public TreeNode buildTree(int[] inOrder, int[] postOrder, int nElements, int startInOrder, int startPostOrder)
{
if (nElements==0)
return null;
int rootVal = postOrder[startPostOrder+nElements-1];
TreeNode root = new TreeNode(rootVal);
if(nElements==1)
return root;
for(int i=0; i<nElements; i++)
{
if(inOrder[startInOrder+i]==rootVal)
{
root.left = buildTree(inOrder, postOrder, i, startInOrder, startPostOrder);
root.right = buildTree(inOrder, postOrder, nElements-i-1, startInOrder+i+1, startPostOrder+i);
break;
}
}
return root;
}
}
No comments :
Post a Comment