难度中等726
给定两个整数数组?inorder?和?postorder?，其中?inorder?是二叉树的中序遍历，?postorder?是同一棵树的后序遍历，请你构造并返回这颗?二叉树?。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder?和?postorder?都由?不同?的值组成postorder?中每一个值都在?inorder?中inorder?保证是树的中序遍历postorder?保证是树的后序遍历
?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private int findPosition(int[] arr, int start, int end, int key) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
//root位置是position
//in[] instart,...,position- 1,root,... inend -1,inend
//post[] poststart,...,postion-1-instart+poststart,...,postend,root
private TreeNode myBuildTree(int[] inorder, int instart, int inend,
int[] postorder, int poststart, int postend) {
if (instart > inend) {
return null;
}
TreeNode root = new TreeNode(postorder[postend]);
int position = findPosition(inorder, instart, inend, postorder[postend]);
root.left = myBuildTree(inorder, instart, position - 1,
postorder, poststart, poststart + position - instart - 1);
root.right = myBuildTree(inorder, position + 1, inend,
postorder, poststart + position - instart, postend - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length != postorder.length) {
return null;
}
return myBuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
}
