Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
You may assume that duplicates do not exist in the tree.
Solution:O(n)
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd){
if(inStart > inEnd || postStart > postEnd)
return null;
int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);
int k=0;
for(int i=0; i< inorder.length; i++){
if(inorder[i]==rootValue){
k = i;
break;
}
}
root.left = buildTree(inorder, inStart, k-1, postorder, postStart, postStart+k-(inStart+1));
root.right = buildTree(inorder, k+1, inEnd, postorder, postStart+k-inStart, postEnd-1);
return root;
}
}
沒有留言:
張貼留言