废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【重建二叉树】,使用【二叉树】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。
名曲目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍。
依据前序与中序遍历序列重建二叉树【MID】
依据前序和中序的特性查找
题干
解题思路
只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位
- 首先通过前序遍历拿到当前树的根节点
对应题目中的结果就是:
- 因为中序遍历中根节点的左边是左子树,右边是右子树,所以可以依据根节点在中序遍历中的位置,知道左右子树的范围
代码实现
给出代码实现基本档案
基本数据结构:二叉树
辅助数据结构:哈希表
算法:递归
技巧:无
其中数据结构、算法和技巧分别来自:
- 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧:双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { // 0 设置中序遍历 值-元素位置 的map,因为题目确保了无重复元素 private Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();; /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param preOrder int整型一维数组 * @param vinOrder int整型一维数组 * @return TreeNode类 */ public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) { // 1 条件判断 if (preOrder == null || preOrder.length < 1 || vinOrder == null || vinOrder.length < 1) { return null; } // 2 构建中序遍历的哈希映射 int length = preOrder.length; for (int i = 0; i < length; i++) { indexMap.put(vinOrder[i], i); } // 递归获取左右子树 return rebuildTree(preOrder, 0, length - 1, vinOrder, 0, length - 1); } private TreeNode rebuildTree(int[] preOrder, int preLeft, int preRight, int[] inOrder, int inLeft, int inRight) { // 0 设置递归终止条件 if (preLeft > preRight) { return null; } // 1 首先构建根节点,也就是前序遍历的第一个元素 TreeNode root = new TreeNode(preOrder[preLeft]); // 找到根节点在中序集合中的位置 int pIndex = indexMap.get(preOrder[preLeft]); // 明确左子树的节点数量 int leftSize = pIndex - inLeft; // 2 递归构建根节点的左子树: root.left = rebuildTree(preOrder, preLeft + 1, preLeft + leftSize, inOrder, inLeft, pIndex - 1); // 3 递归构建根节点的右子树: root.right = rebuildTree(preOrder, preLeft + leftSize + 1, preRight, inOrder, pIndex + 1, inRight); return root; } }
复杂度分析
时间复杂度:遍历了一遍二叉树,时间复杂度O(N);
空间复杂度:使用了辅助数据结构哈希表,空间复杂度O(N),递归栈深度极端情况下为O(N),综合来看还是O(N)