1.题目链接

根据一棵树的中序遍历与后序遍历构造二叉树

2.题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

/
9 20
/
15 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3.题解

/**
 * 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;
 *     }
 * }
 */
class Solution {
  public int  postindex =0;
    public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
if(inbegin>inend){return null;}
TreeNode root=new TreeNode(postorder[postindex]);
int inkey=findkey(inorder,postorder[postindex],inbegin,inend);
postindex--;
root.right=buildTreeChild(postorder,inorder,inkey+1,inend);
root.left=buildTreeChild(postorder,inorder,inbegin,inkey-1);




return root;
    }

  public int  findkey(int[] inorder,int key,int inbegin,int inend){
      for(int i=inbegin;i<=inend;i++){
          if(inorder[i]==key){
              return i;
          }
      }
      return -1;
  }
  public TreeNode buildTree(int[] inorder, int[] postorder) {
      postindex=postorder.length-1;
if(postorder==null||inorder==null){
    return null;
}
return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
}