0889. Construct Binary Tree from Preorder and Postorder Traversal¶
题目信息¶
- 题号:
0889
- 难度:
Medium
- 主题:
二叉树、前序遍历、后序遍历
- 原题:
- 重点:
输入值互不相同且两种遍历来自同一棵树;前序与后序不一定唯一确定结构,返回任意一棵匹配的二叉树即可
题目重述¶
给定两个等长整数数组 preorder 和 postorder,它们分别是一棵二叉树的前序遍历和后序遍历。前序顺序为“根、左子树、右子树”,后序顺序为“左子树、右子树、根”。
所有节点值互不相同,两个数组包含相同的一组值,并保证至少存在一棵二叉树产生这两种遍历。请构造并返回任意一棵符合条件的树。当前序和后序无法区分某个唯一孩子位于左侧还是右侧时,多个不同结构都属于合法答案。
1 <= preorder.length == postorder.length <= 30,节点值在 [1, preorder.length] 范围内且互不相同。
自建示例¶
只有单孩子时结构可能不唯一:
输入:preorder = [1,2,3], postorder = [3,2,1]
输出:root = [1,2,null,3]
解释:该输出表示节点 1 的左孩子为 2,节点 2 的左孩子为 3,前序和后序分别与输入一致。把某些唯一孩子放到右侧也可能产生同样的两种遍历,因此其他合法结构也可接受。
根节点同时具有左右子树:
输入:preorder = [4,2,1,3,5], postorder = [1,3,2,5,4]
输出:root = [4,2,5,1,3]
解释:该树的前序遍历依次为 4、2、1、3、5,后序遍历依次为 1、3、2、5、4,与输入完全一致。