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

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;
}
}