剑指Offer（四）重建二叉树（Java版 )

朱雀 2021-09-26 21:54 275阅读 0赞

# 一、题目描述 #

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

# 二、问题分析 #

根据前序遍历和中序遍历的特点，可以知道根节点、左子树和右子树。同样的方法继续从左子树里面找到根节点、左子树和右子树，层层递归，实现重建。  
![这里写图片描述][70]  
这里再看画几张图：  
对右子树进行再次递归：  
![这里写图片描述][70 1]  
分析出：  
![这里写图片描述][70 2]  
结合下面的代码，应该就可以理解了

# 三、代码分析 #

public class Solution {
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            int i=0;
            //确保不能超出边界
            if(pre.length!=in.length||pre.length==0||in.length==0)
                return null;
            //根节点是前序遍历数组的第一个元素
            TreeNode root = new TreeNode(pre[0]);
            //中序遍历数组里面等于前序遍历数组第一个元素的节点是根节点
            while(in[i]!=root.val)
                i++;
            //得到i之后，就可以得出左子树的元素个数和右子树的元素个数
            int[] preLeft = new int[i];
            int[] inLeft = new int[i];
            int[] preRight = new int[pre.length-i-1];
            int[] inRight = new int[in.length-i-1];
            //依次将左子树和右子树数组进行填充
            for(int j = 0;j<in.length;j++) {
                if(j<i) {
                    //前序遍历左子树等于前序数组第一个元素之后的i个值
                    preLeft[j] = pre[j+1];
                    //中序遍历左子树等于中序数组的前i个值
                    inLeft[j] = in[j];
                } else if(j>i) {
                    //前序遍历右子树等于前序数组第i个元素之后值
                    preRight[j-i-1] = pre[j];
                    //中序遍历右子树等于中序数组的第i个元素之后值
                    inRight[j-i-1] = in[j];
                }
            }
            //将前序遍历的左子树和中序遍历的左子树进行再次递归
            root.left = reConstructBinaryTree(preLeft,inLeft);
            //将前序遍历的右子树和中序遍历的右子树进行再次递归
            root.right = reConstructBinaryTree(preRight,inRight);
            return root;
        }
    }

# 四、运行结果 #

![这里写图片描述][70 3]

[70]: /images/20210923/dfcdadcb6f9d405fa1042e21ca1c46f3.png
[70 1]: /images/20210923/8b83e3dd4c6948d4a39c093babcb3f0f.png
[70 2]: /images/20210923/f07a383edae4460d8cefe1943c139a07.png
[70 3]: /images/20210923/b1268248cc13480285e88a33a01035df.png