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