根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
代码语言：javascript复制中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7解：跟105题差不多
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public TreeNode buildTree2(int[] inorder, int[] postorder) {
return build2(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build2(int[] inorder, int[] postorder, int postEnd, int inSt, int inEnd) {
//递归临界点
if (postEnd < 0 || inSt > inEnd) {
return null;
}
//后序遍历尾节点为根节点
TreeNode rootNode = new TreeNode(postorder[postEnd]);
//根节点在中序遍历的索引
int rootIndex = 0;
for (int i = inSt; i <= inEnd; i ) {
if (inorder[i] == rootNode.val) {
rootIndex = i;
break;
}
}
int rightLength = inEnd - rootIndex;
int postEndLeft = postEnd - rightLength - 1;
int postEndRight = postEnd - 1;
rootNode.left = build2(inorder, postorder, postEndLeft, inSt, rootIndex - 1);
rootNode.right = build2(inorder, postorder, postEndRight, rootIndex 1, inEnd);
return rootNode;
}
