做公司网站的,腾度淄博网站建设,网络推广的手段,对网站主要功能界面进行赏析系列文章目录 文章目录 系列文章目录前言 前言
前些天发现了一个巨牛的人工智能学习网站#xff0c;通俗易懂#xff0c;风趣幽默#xff0c;忍不住分享一下给大家。点击跳转到网站#xff0c;这篇文章男女通用#xff0c;看懂了就去分享给你的码吧。 描述 给定节点数为…系列文章目录 文章目录 系列文章目录前言 前言
前些天发现了一个巨牛的人工智能学习网站通俗易懂风趣幽默忍不住分享一下给大家。点击跳转到网站这篇文章男女通用看懂了就去分享给你的码吧。 描述 给定节点数为 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,i1),Arrays.copyOfRange(in,0,i));//将右子树看成一棵二叉树调用该方法可以得到右子树根结点即上面根结点的右子结点root.right reConstructBinaryTree(Arrays.copyOfRange(pre,i1,pre.length),Arrays.copyOfRange(in,i1,in.length));//找到根结点位置便跳出循环break;}}//返回根结点return root;}
}
