重建二叉树java

我们知道，可以通过二叉树的前序遍历、中序遍历、后序遍历可以确定唯一的一颗二叉树。事实上我们可以从前序/中序，后序/中序得到一颗唯一的二叉树，而前序/后序得到的二叉树不唯一（读者可以自行验证）

注意：以下讨论均在节点值不重复的前提条件下

1. 根据后序/中序

后序遍历序列：后序遍历序列的最后一个节点是树的根节点root，可以定义一个哈希表存储中序遍历的值（节点值不重复），通过root找到中序遍历中根节点的位置，由左子树|root|右子树，确定中序遍历左子树和右子树的边界位置

中序遍历序列：由中序遍历的左子树和右子树，可以确定左子树和右子树在后序遍历的边界位置

class Solution {

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

public TreeNode buildTree(int[] inorder, int[] postorder) {

if(inorder.length == 0){

return null;

}

for(int i = 0;i<inorder.length;i++){

map.put(inorder[i],i);

}

return helper(inorder,postorder,0,inorder.length-1,0,postorder.length-1);

}

private TreeNode helper(int[] inorder,int[] postorder,int inL,int inR,int poL,int poR){

if(inL>inR || poL>poR){

return null;

}

TreeNode root = new TreeNode(postorder[poR]);

int index = map.get(root.val);

int lefttree = index - inL ;

root.left = helper(inorder,postorder,inL,index-1,poL,poL+lefttree-1);

root.right = helper(inorder,postorder,index+1,inR,poL+lefttree,poR-1);

return root;

}

}

2 前序/中序

前面已经分析了，直接套！

HashMap<Integer, Integer> dic = new HashMap<>();

int[] po;

public TreeNode buildTree(int[] preorder, int[] inorder) {

po = preorder;

for(int i = 0; i < inorder.length; i++)

dic.put(inorder[i], i);

return recur(preorder,inorder,0, preorder.length - 1, 0,inorder.length-1);

}

TreeNode recur(int[] preorder, int[] inorder,int preL, int preR,int inL,int inR) {

if(preL > preR || inL>inR) return null;

TreeNode root = new TreeNode(preorder[preL]);

int i = dic.get(root.val);

int lefttree = i - inL;

root.left = recur(preorder,inorder, preL+1,preL +lefttree, inL,inL+lefttree);

root.right = recur(preorder,inorder,preL+lefttree+1,preR,inL+lefttree+1,inR);

return root;

}

3 前序/后序

讨论其中一种情况即可，基本就是套下来了

class Solution {

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

public TreeNode buildTree(int[] inorder, int[] postorder) {

if(inorder.length == 0){

return null;

}

for(int i = 0;i<inorder.length;i++){

map.put(inorder[i],i);

}

return helper(inorder,postorder,0,inorder.length-1,0,postorder.length-1);

}

private TreeNode helper(int[] inorder,int[] postorder,int inL,int inR,int poL,int poR){

if(inL>inR || poL>poR){

return null;

}

TreeNode root = new TreeNode(postorder[poR]);

int index = map.get(root.val);

int lefttree = index - inL ;

root.left = helper(inorder,postorder,inL,index-1,poL,poL+lefttree-1);

root.right = helper(inorder,postorder,index+1,inR,poL+lefttree,poR-1);

return root;

}

}