题目
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2, 4, 7, 3, 5, 6, 8}
和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}
,则重建出二叉树并输出它的头结点。
解答1[Java]:递归
1 | import java.util.HashMap; |
曾经想把这里:
1 | if (leftOfPre > rightOfPre) |
修改为 if (leftOfPre == rightOfPre)
,后来发现不行,因为 leftOfPre
和 rightOfPre
不是线性变化的,有可能不会出现两者相等的情况。例如,如果一颗只有左子树没有右子树的二叉树,第一次递归的时候在重建右子树的时候就会导致 leftOfPre
大于 rightOfPre
。
另外一道类似的题目:[编程题]二叉树遍历 - 牛客网