欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

根据前序遍历和中序遍历,后序遍历和中序遍历重构二叉树

程序员文章站 2022-05-06 21:22:07
...

重构二叉树目前主要是采取递归的方式
只能通过前序,中序 或者 后续,中序进行重构
前序和后序是不能够重构的,因为在得知根节点后只有中序遍历才能确定左子树和右子树的数目

二叉树的几种遍历
前序遍历:根结点 —> 左子树 —> 右子树

中序遍历:左子树—> 根结点 —> 右子树

后序遍历:左子树 —> 右子树 —> 根结点

层次遍历:只需按层次遍历即可

根据前序遍历和中序遍历重构二叉树:

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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;
    }
}