0889. Construct Binary Tree from Preorder and Postorder Traversal

题目信息

题号:

0889

难度:

Medium

主题:

二叉树、前序遍历、后序遍历

原题:

LeetCode 0889

重点:

输入值互不相同且两种遍历来自同一棵树;前序与后序不一定唯一确定结构,返回任意一棵匹配的二叉树即可

题目重述

给定两个等长整数数组 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,与输入完全一致。