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