NC重建二叉树

系列文章目录

---

---

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

---

描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
思路：
前序遍历：根→左→右
中序遍历：左→根→右

由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1；
则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1，便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树；
递归调用：将左子树和右子树分别看成一颗树，将其前序遍历序列、中序遍历序列分别传入到该方法中，便可得到左子树的根结点、右子树的根结点。此时需要用第一步得到的根结点连接它们；
递归调用的终止条件：直到传入数组为空，说明已经没有节点，直接返回null。
答案：

import java.util.Arrays;
public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] in) {//递归调用的终止条件if(pre.length == 0 || in.length == 0){return null;}//由前序遍历得到该二叉树的根结点TreeNode root = new TreeNode(pre[0]);//在中序遍历中找根结点位置，进行左右子树的划分for(int i = 0; i < in.length; i++){if(root.val == in[i]) {//将左子树看成一棵二叉树调用该方法，可以得到左子树根结点，即上面根结点的左子结点root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));//将右子树看成一棵二叉树调用该方法，可以得到右子树根结点，即上面根结点的右子结点root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));//找到根结点位置便跳出循环break;}}//返回根结点return root;}
}