0889. 根据前序和后序遍历构造二叉树 #
- 标签:树、数组、哈希表、分治、二叉树
- 难度:中等
题目大意 #
描述:给定一棵无重复值二叉树的前序遍历结果 preorder
和后序遍历结果 postorder
。
要求:构造出该二叉树并返回其根节点。如果存在多个答案,则可以返回其中任意一个。
说明:
- $1 \le preorder.length \le 30$。
- $1 \le preorder[i] \le preorder.length$。
preorder
中所有值都不同。postorder.length == preorder.length
。- $1 \le postorder[i] \le postorder.length$。
postorder
中所有值都不同。- 保证
preorder
和postorder
是同一棵二叉树的前序遍历和后序遍历。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归 #
如果已知二叉树的前序遍历序列和后序遍历序列,是不能唯一地确定一棵二叉树的。这是因为没有中序遍历序列无法确定左右部分,也就无法进行子序列的分割。
只有二叉树中每个节点度为 2
或者 0
的时候,已知前序遍历序列和后序遍历序列,才能唯一地确定一颗二叉树,如果二叉树中存在度为 1
的节点时是无法唯一地确定一棵二叉树的,这是因为我们无法判断该节点是左子树还是右子树。
而这道题说明了,如果存在多个答案,则可以返回其中任意一个。
我们可以默认指定前序遍历序列的第 2
个值为左子树的根节点,由此递归划分左右子序列。具体操作步骤如下:
-
从前序遍历序列中可知当前根节点的位置在
preorder[0]
。 -
前序遍历序列的第
2
个值为左子树的根节点,即preorder[1]
。通过在后序遍历中查找上一步根节点对应的位置postorder[k]
(该节点右侧为右子树序列),从而将二叉树的左右子树分隔开,并得到左右子树节点的个数。 -
从上一步得到的左右子树个数将后序遍历结果中的左右子树分开。
-
构建当前节点,并递归建立左右子树,在左右子树对应位置继续递归遍历并执行上述三步,直到节点为空。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n^2)$。