根据前序遍历和中序遍历,后序遍历和中序遍历重构二叉树
重构二叉树目前主要是采取递归的方式
只能通过前序,中序 或者 后续,中序进行重构
前序和后序是不能够重构的,因为在得知根节点后只有中序遍历才能确定左子树和右子树的数目
二叉树的几种遍历
前序遍历:根结点 —> 左子树 —> 右子树
中序遍历:左子树—> 根结点 —> 右子树
后序遍历:左子树 —> 右子树 —> 根结点
层次遍历:只需按层次遍历即可
根据前序遍历和中序遍历重构二叉树:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
前序遍历第一位是根节点;
中序遍历中,根节点左边的是根节点的左子树,右边是根节点的右子树。
所以,根节点 是{ 1 };
左子树是:前序{ 2,4,7 } ,中序{ 4,7,2 };
右子树是:前序{ 3,5,6,8 } ,中序{ 5,3,8,6 };
根据这个我们可以得出二叉树的形状
这时,如果我们把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
这样,一直用这个方式,就可以实现重建二叉树。
解题步骤
1、前序遍历的第一个节点即为根节点
2、根据根节点,在中序遍历中找出左子树和右子树,并统计左子树和右子树的个数
3、递归构建左子树和右子树
根据前序遍历得出根节点,根据中序遍历确定左子树和右子树的个数
public class RebuildBinaryTree {
//假设输入的前序遍历和中序遍历的结果中都不含重复的数字
/*
前序遍历第一位是根节点;
中序遍历中,根节点左边的是根节点的左子树,右边是根节点的右子树。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
首先,根节点 是{ 1 };
左子树是:前序{ 2,4,7 } ,中序{ 4,7,2 };
右子树是:前序{ 3,5,6,8 } ,中序{ 5,3,8,6 };
这时,如果我们把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||in==null){
return null;
}
TreeNode treeNode=reConstructBinaryTree(pre, in,0,pre.length-1,0,in.length-1);
return treeNode;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in,int preStart,int preEnd,int inStart,int inEnd) {
TreeNode tree=new TreeNode(pre[preStart]); //前序遍历的第一个是根节点,递归时把左子树和右子树分别作为新的二叉树
tree.left=null;
tree.right=null;
if(preStart==preEnd&&inStart==inEnd){ //说明已经是树叶节点
return tree;
}
int root;
for(root=inStart;root<inEnd;root++){ //寻找根节点在中序遍历中的下标
if(pre[preStart]==in[root]){
break;
}
}
int leftLength=root-inStart; //左子树的长度
int rightLength=inEnd-root; //右子树的长度
//把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
if(leftLength>0){
tree.left=reConstructBinaryTree(pre,in,preStart+1,preStart+leftLength,inStart,root-1);
}
if(rightLength>0){
tree.right=reConstructBinaryTree(pre,in,preStart+1+leftLength,preEnd,root+1,inEnd);
}
return tree;
}
}
根据后序遍历和中序遍历重构二叉树:
输入某二叉树的后序遍历和中序遍历的结果,请重建出该二叉树。假设输入的后序遍历和中序遍历的结果中都不含重复的数字。例如输入后序遍历序列{7,4,2,5,8,3,6,1}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
思路是一样的:
解题步骤
1、后序遍历的最后一个节点即为根节点
2、根据根节点,在中序遍历中找出左子树和右子树,并统计左子树和右子树的个数
3、递归构建左子树和右子树
public class RebuildBinaryTree {
//假设输入的后序遍历和中序遍历的结果中都不含重复的数字
/*
后序遍历最一位是根节点;
中序遍历中,根节点左边的是根节点的左子树,右边是根节点的右子树。
例如输入后序遍历序列{7,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}。
首先,根节点 是{ 1 };
左子树是:后序{ 7,4,2} ,中序{ 4,7,2 };
右子树是:后序{ 5,8,6,3} ,中序{ 5,3,8,6 };
这时,如果我们把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
*/
public TreeNode reConstructBinaryTree(int [] end,int [] in) {
if(end==null||in==null){
return null;
}
TreeNode treeNode=reConstructBinaryTree(end, in,0,end.length-1,0,in.length-1);
return treeNode;
}
public TreeNode reConstructBinaryTree(int [] end,int [] in,int endStart,int endEnd,int inStart,int inEnd) {
TreeNode tree=new TreeNode(end[endEnd]); //后序遍历的最后一个是根节点,递归时把左子树和右子树分别作为新的二叉树
tree.left=null;
tree.right=null;
if(endStart==endEnd&&inStart==inEnd){ //说明已经是树叶节点
return tree;
}
int root;
for(root=inStart;root<inEnd;root++){ //寻找根节点在中序遍历中的下标
if(end[endStart]==in[root]){
break;
}
}
int leftLength=root-inStart; //左子树的长度
int rightLength=inEnd-root; //右子树的长度
//把左子树和右子树分别作为新的二叉树,则可以求出其根节点,左子树和右子树。
if(leftLength>0){
tree.left=reConstructBinaryTree(end,in,endStart,endStart+leftLength-1,inStart,root-1);
}
if(rightLength>0){
tree.right=reConstructBinaryTree(end,in,root,endEnd-1,root+1,inEnd);
}
return tree;
}
}
上一篇: 如何用IDEA一步一步开发WebService客户端程序
下一篇: Flask登录注册界面美化
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
c/c++ 用前序和中序,或者中序和后序,创建二叉树
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
c++智能指针和二叉树(1): 图解层序遍历和逐层打印二叉树
-
L2-006 树的遍历 (后序中序求层序)