题目
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
1
2 前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树:
1
2
3
4
5 3
/ \
9 20
/ \
15 7限制:
0 <= 节点个数 <= 5000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
二刷这道题。
前序遍历首元素为根节点。
中序遍历中,根节点将树分为左子树右子树。
前序遍历顺序:根节点->左子树->右子树,知道左右子树元素数量即可一刀切把数组划为左右子树。前序遍历根据元素数量切,中序遍历从根节点切。
测试用例
- 非法输入(两数组长度不等)
- 空输入
- 常规输入
实现
1 | /** |
- 时间复杂度:$O(N^2)$
- 空间复杂度:$O(N)$
之所以空间复杂度高,是因为find
进行了重复的查找操作,牺牲空间,使用哈希表可以将时间复杂度优化为$O(N)$。
1 | /** |
测试时间减半。