输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中==都不含重复的数字==。
示例:
示例 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 示例 2: Input: preorder = [-1], inorder = [-1] Output: [-1]
主要思路:
在中序遍历中搜索根节点node的索引 ,可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ]
根据中序遍历中的左 / 右子树的节点数量,可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ]可确定 三个节点 :1.树的根节点、2.左子树根节点、3.右子树根节点。
在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,我们可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,我们就只需要 O(1) 的时间对根节点进行定位了。
时间复杂度:O(n),其中 n是树中的节点个数。
空间复杂度:O(n),除去返回的答案需要的 O(n) 空间之外,还需要使用 O(n)的空间存储哈希映射,以及 O(h)(其中 h是树的高度)的空间表示递归时栈空间。这里 h < n,所以总空间复杂度为 O(n)。