题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树：
3
/ \
9 20
/ \
15 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解及思路
源码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return dfs(inorder,postorder,postorder.length-1,0,inorder.length-1);
}
private TreeNode dfs(int[] inorder,int[]postorder,int postEnd,int inStart,int inEnd){
if(inStart>inEnd){
return null;
}
int nodeVal = postorder[postEnd];
TreeNode node = new TreeNode(nodeVal);
int inIndex = 0;
for(int i = inIndex;i<=inEnd;i++){
if(inorder[i]==nodeVal){
inIndex = i;
break;
}
}
TreeNode left = dfs(inorder,postorder,postEnd-(inEnd-inIndex)-1,inStart,inIndex-1);
TreeNode right = dfs(inorder,postorder,postEnd-1,inIndex+1,inEnd);
node.left = left;
node.right = right;
return node;
}
}
