代码随想录：从中后/中前遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

用分治思想，后序遍历是左右中，中序遍历是左中右，后序遍历的最后一个元素就是根节点，

在中序遍历中找到它的位置，它前面的为左子树，后面的为右子树，并能计算左右子树结点个数，算下标差即可，然后递归算每一棵子树，当成一棵树来处理，中序遍历对应前几个结点与后序遍历前几个结点为一棵树上的结点。

/**
 * 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 {
    HashMap<Integer,Integer> m=new HashMap<>();
    int[] post;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i=0;i<inorder.length;i++)
{
    m.put(inorder[i],i);
}
        post=postorder;
       return tree(0,inorder.length-1,0,postorder.length-1);
    }
    TreeNode tree (int inbegin,int inend,int pbegin ,int pend)
    {
        if(inbegin>inend||pbegin>pend)return null;
        TreeNode cur=new TreeNode(post[pend]);
        int idx=m.get(post[pend]);
        cur.left=tree(inbegin,idx-1,pbegin,pbegin+idx-inbegin-1);
        cur.right=tree(idx+1,inend,pbegin+idx-inbegin,pend-1);
        return cur;
    }
}

105. 从前序与中序遍历序列构造二叉树

类似

/**
 * 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 {
    HashMap<Integer,Integer> m= new HashMap<>();
    int[] pre;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++)
          m.put(inorder[i],i);
          pre=preorder;
          return traval(0,inorder.length-1,0,preorder.length-1);
    }
    TreeNode traval(int inbegin,int inend,int pbegin,int pend)
{
    if (inbegin>inend||pbegin>pend)return null;
    TreeNode cur=new TreeNode(pre[pbegin]);
    int idx=m.get(pre[pbegin]);
    cur.left=traval(inbegin,idx-1,pbegin+1,pbegin+idx-inbegin);
    cur.right=traval(idx+1,inend,pbegin+idx-inbegin+1,pend);
    return cur;
}
}