Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
一刷
思路同105
/**
* Definition for a binary tree node.
* 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 helper(inorder, 0, inorder.length-1, postorder, inorder.length-1);
}
private TreeNode helper(int[] inorder, int inStart, int inEnd, int[] postorder, int pEnd){
if(inStart>inEnd) return null;
if(inEnd>=inorder.length) return null;
if(pEnd >= postorder.length) return null;
TreeNode root = new TreeNode(postorder[pEnd]);
int index = 0;
for(index = inStart; index<= inEnd; index++){
if(inorder[index] == root.val) break;
}
root.left = helper(inorder, inStart, index-1, postorder, pEnd-inEnd+index-1);
root.right = helper(inorder, index+1, inEnd, postorder, pEnd-1);
return root;
}
}
