剑指offer打卡 JZ7 重建二叉树

本文主要是介绍剑指offer打卡 JZ7 重建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在牛客网刷的，还是跟leetcode一样非acm模式，由于急着暑期实习题量不固定，八股算法轮刷

打卡内容偏个人笔记，本人水平一般(代码随想录稀里糊涂刷了一遍)，从小白开始分析(甚至会分析语法)，尽量一题多解深入探究(一般ac后看看前三个题解发散下思维)，希望能对你有帮助

JZ7 重建二叉树

描述

给定节点数为 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.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000，节点的值 −10000≤val≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

分析

思路数据结构都学过，前序找根节点，中序分割子树

代码刷过再写还是没过，主要不知道写递归还是循环，并且根节点的处理感觉很特殊

于是火速看了算法笔记的二叉树构造部分，记录在我主页算法笔记专栏

上上行提到的问题，还是应该写递归，可以看到同颜色的块是等长的且一个是前序一个是中序，递归参数设置为数组、起始位置和终止位置即可

于是采用前序遍历，做的事是找到inOrder中根节点位置用于后续区间分割

由于有返回值，需要修改代码模板，尽管是前序遍历，在递归函数最后要return root

代码如下：

public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {TreeNode root = build(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);return root;
}TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {if (preStart > preEnd) return null;// Find the index of root node in inorder traversalint index = 0;for (int i = inStart; i <= inEnd; i++) {if (in[i] == pre[preStart]) {index = i;break;}}int leftSize = index - inStart;TreeNode root = new TreeNode(pre[preStart]);root.left = build(pre, preStart + 1, preStart + leftSize, in, inStart, index - 1);root.right = build(pre, preStart + leftSize + 1, preEnd, in, index + 1, inEnd);return root;
}

这篇关于剑指offer打卡 JZ7 重建二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---