解决方案


方法一:深度优先遍历

思路

当做先序遍历的时候,我们可能会翻转某一个节点,尝试使我们当前的遍历序列与给定的行程序列相匹配。

如果我们希望先序遍历序列的下一个数字是 voyage[i] ,那么至多只有一种可行的遍历路径供我们选择,因为所有节点的值都不相同。

算法

进行深度优先遍历。如果遍历到某一个节点的时候,节点值不能与行程序列匹配,那么答案一定是 [-1]

否则,当行程序列中的下一个期望数字 voyage[i] 与我们即将遍历的子节点的值不同的时候,我们就要翻转一下当前这个节点。

复杂度分析

  • 时间复杂度:,其中 是给定树中节点的数量。

  • 空间复杂度: