题目106. Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
1,
在盗用一图
IMG_20161227_173459.jpg
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder == null || postorder.length == 0){
return null;
}
return createTree(postorder, postorder.length-1, inorder, 0, inorder.length-1);
}
private TreeNode createTree(int[] postorder ,int postIdx, int[] inorder, int inStartIdx, int inEndIdx){
if(postIdx < 0){
return null;
}
if(inStartIdx > inEndIdx){
return null;
}
int rootVal = postorder[postIdx];
TreeNode root = new TreeNode(rootVal);
int rootIdxIn;
for(rootIdxIn=inStartIdx; rootIdxIn<=inEndIdx; rootIdxIn++){
if(rootVal == inorder[rootIdxIn]){
break;
}
}
root.left = createTree(postorder,postIdx-(inEndIdx-rootIdxIn)-1,inorder,inStartIdx,rootIdxIn-1);
root.right = createTree(postorder,postIdx-1,inorder,rootIdxIn+1,inEndIdx);
return root;
}
}
