引言：已知一颗二叉树的前序、中序、后序遍历，我们知道如何还原出这颗二叉树，那么我们使用Java代码如何实现？
备注：
根据二叉树的先序、中序、后序遍历构建二叉树-图文详解
/**
* 下文中用到的TreeNode类
*/
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
根据二叉树的前序、中序遍历还原二叉树
public TreeNode buildTree (int[] preorder, int[] inorder) {
// write code here
return buildNode(preorder,0,preorder.length,inorder,0,inorder.length);
}
private TreeNode buildNode(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight){
//没有元素了。
if(inRight - inLeft < 1){
return null;
}
//只有一个元素了。
if(inRight - inLeft == 1) {
return new TreeNode(inorder[inLeft]);
}
// 前遍历的第一个节点是根节点
int rootVal = preorder[preLeft];
TreeNode rootNode = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int rootIndex = 0;
for (int i = inLeft; i < inRight ; i++) {
if(inorder[i] == rootVal){
rootIndex = i;
break;
}
}
//根据rooIndex划分左右子树
//划分左右中序数组：根据切割点rootIndex划分中序数组
//划分左右前序数组：根据中序数组的大小必然是和前序数组的大小是一样的。
int length = rootIndex - inLeft;
rootNode.left = buildNode(preorder,preLeft + 1,preLeft + 1 + length,inorder,inLeft,rootIndex);
rootNode.right = buildNode(preorder,preLeft + 1 + length,preRight,inorder,rootIndex + 1,inRight);
return rootNode;
}
根据二叉树的中、后序遍历还原二叉树
public TreeNode buildTree (int[] inorder, int[] postorder) {
// write code here
return buildNode(inorder,0,inorder.length,postorder,0,postorder.length);
}
private TreeNode buildNode(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight){
//没有元素了。
if(inRight - inLeft < 1){
return null;
}
//只有一个元素了。
if(inRight - inLeft == 1) {
return new TreeNode(inorder[inLeft]);
}
// 后序遍历的最后一个节点是根节点
int rootVal = postorder[postRight - 1];
TreeNode rootNode = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int rootIndex = 0;
for (int i = inLeft; i < inRight ; i++) {
if(inorder[i] == rootVal){
rootIndex = i;
break;
}
}
//根据rooIndex划分左右子树
//划分左右中序数组：根据切割点rootIndex划分中序数组
//划分左右后序数组：根据中序数组的大小必然是和后序数组的大小是一样的。
int length = rootIndex - inLeft;
rootNode.left = buildNode(inorder,inLeft,rootIndex,postorder,postLeft,postLeft + length);
rootNode.right = buildNode(inorder,rootIndex + 1,inRight,postorder,postLeft + length, postRight - 1);
return rootNode;
}
