使用后序遍历和叶节点数组创建先序遍历

输入中，我们有两个给定的数组。一个数组是代表二叉树后序遍历的整数数组，另一个数组是提供叶节点信息的布尔数组。后序数组中的每个元素都有一个对应的叶节点数组中的布尔值。如果布尔数组中的值为 true，则给定的元素将构成二叉树中的叶节点；否则，则不是。我们的任务是显示输入中给定的后序遍历的二叉树的前序遍历。请注意，可能存在多个具有相同后序遍历的二叉树。必须考虑其中任意一个二叉树，并根据该二叉树显示前序遍历到控制台。

示例 1

输入

后序遍历 = { 140, 120, 150, 160, 130, 110, 170 }

isLeaf = { true, false, true, true, false, false, false }

输出 { 170, 110, 120, 140, 130, 150, 160 }

方法

概念是首先借助后序序列的最后一个键来识别二叉树的根节点。然后借助给定的布尔数组，我们检查根节点是叶节点还是内部节点。如果根节点是内部节点，则递归创建其左子树和右子树。以下是上述方法的实现。

文件名： CreatePreorder.java

输出

For a tree whose post order traversal is: 
140 120 150 160 130 110 170  
 
The preorder traversal is: 
170 110 120 140 130 150 160

复杂度分析：程序的时间复杂度和空间复杂度都是 O(n)，其中 n 是前序遍历数组中元素的数量。