题目内容

给定二叉树前序遍历和中序遍历的字符串，以及需要删除的节点，要求先解析这两个字符串获取对应二叉树，再做删除指定节点操作，然后输出该二叉树的后序遍历结果。删除节点规则：

$1$、指定节点是根节点，则不做删除操作；

$2$、指定节点是叶子节点，则直接删除；

$3$、指定节点是内部节点：

（$1$）如果是左子节点，则把该节点的左子树挂接到它的父节点，然后删除该节点以及它的右子树；

（$2$）如果是右子节点，则把该节点的右子树挂接到它的父节点，然后删除该节点以及它的左子树。

输入描述

$string$ $preorderStr$ // 前序遍历字符串

$string$ $inorderStr$ // 中序遍历字符串

$char$ $beDeletedNode$ // 待删除的节点

输出描述

$string$ $outputStr$ // 返回 "" 或者 后序遍历的字符串

注：

$1$、给定的$preorderStr$ 和 $inorderStr$ 是由大写字母组成的字符串，长度为$2$ ~ $26$，每个字母表示一个节点值，且节点值唯一；

$2$、给定的 $beDeletedLeafNode$ 是一个大写字母，如果输入的不是大写字母、或者找不到对应节点、或者找到的节点是根节点，都不做删除操作；

$3$、如果做了删除操作，则输出删除叶子节点后的二叉树后序遍历结果，否则直接输出二叉树后序遍历结果；

$4$、$preorderStr$ 和 $inorderStr$ 符合如下场景则输出空串""，例如：

（$1$）字符串中存在非大写字母；

（$2$）长度超出范围；

（$3$）节点值不唯一；

（$4$）两个字符串长度不一致；

（$5$）两个字符串元素不相同；

（$6$）无法解析出对应二叉树。

补充说明

$1$、程序运行内存要小于$256$MB；

$2$、程序运行耗时不能超过$1$秒。

样例1

输入

"23a","ABC",A

输出

""

说明

输入存在非法字符串

样例2

输入

"ADE","DAE",E

输出

"DA"

样例3

输入

"AABCD","BAACD",A

输出

""

说明

出现重复节点值

样例4

输入

"ABC","BAC",A

输出

"BCA"

说明

找到的节点 $A$ 是根节点

样例5

输入

"ABCDE","BAHDE",E

输出

""

说明

输入的两个遍历结果元素不相同