Thought:
Root is the last element in the postorder sequence.
Find this value in the inorder sequence.
The elements before it in inorder sequence is the left subtree.
The elements after it in inorder sequence is the right subtree.
Code:
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len = inorder.length;
if(len == 0) return null;
TreeNode root = new TreeNode(postorder[len - 1]);
int i = 0;
for(i = 0; i < len; i ++) {
if(inorder[i] == postorder[len - 1]) break;
}
root.left = buildTree(Arrays.copyOfRange(inorder, 0, i), Arrays.copyOfRange(postorder, 0, i));
root.right = buildTree(Arrays.copyOfRange(inorder, i + 1, len), Arrays.copyOfRange(postorder, i, len - 1));
return root;
}
}
No comments:
Post a Comment