剑指Offer | 重建二叉树

浅浅的花香味﹌ 2022-05-25 10:27 40阅读 0赞

做了个剑指Offer的题目目录，链接如下：  
[https://blog.csdn.net/mengmengdastyle/article/details/80317246][https_blog.csdn.net_mengmengdastyle_article_details_80317246]  
一、题目  
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。  
二、解析  
(1) 遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。  
\- 前序遍历：根节点->左子树->右子树  
\- 中序遍历：左子树->根节点->右子树  
\- 后序遍历：左子树->右子树->根节点  
例如：求下面树的三种遍历  
![这里写图片描述][70]  
\- 前序遍历：a b d e f g c  
\- 中序遍历：d e b g f a c  
\- 后序遍历：e d g f b c a  
（2）对于此题来说给出了前序和中序。  
思路：  
\- 从前序中容易找出根节点；  
\- 以前序的根节点可以将中序中的树分成两部分，在此树前的为根节点的左子树，在此树后的为根节点的右子树；  
（3）图示

三、代码

public class CJTreeNode {
        public static void main(String[] args) {
            int[] pre = {
       1,2,4,7,3,5,6,8};
            int[] in = {
       4,7,2,1,5,3,8,6};
            TreeNode reConstructBinaryTree = reConstructBinaryTree(pre,in);
        }
        public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
            return root;
        }
        //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
        private static TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
            System.out.println("startPre: " + startPre + " ,endPre： " + endPre + " ,startIn: " + startIn + " ,endIn: " + endIn);
            if(startPre>endPre||startIn>endIn)
                return null;
            TreeNode root=new TreeNode(pre[startPre]);
    
            for(int i=startIn;i<=endIn;i++)
                if(in[i]==pre[startPre]){
                    root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                    root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                    //System.out.println("root.left----> startPre+1: " + " ,startIn: " + startIn + " ,i-1: ");
                    //+ (startPre+1) + " ,startPre+i-startIn： " + (startPre+i-startIn)
                    break;
                }
    
            return root;
        }
    }
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246
[70]: /images/20220525/9fe7aae4f0e94ff981c6b0851c23076e.png