0971. Flip Binary Tree To Match Preorder Traversal

题目信息

题号:

0971

难度:

Medium

主题:

二叉树、先序遍历、左右子树翻转

原题:

LeetCode 0971

重点:

在节点上翻转会交换其左右子树;需要用最少翻转使最终先序遍历等于 voyage,返回翻转节点值,无法匹配时返回 [-1]

题目重述

给定含 n 个节点的二叉树根节点 root 和长度为 n 的整数数组 voyage。树中节点分别拥有 1 至 n 的唯一值,voyage 也由这些值各组成一次。可以在任意节点执行翻转操作,交换该节点的左子树和右子树。

请翻转最少数量的节点,使操作后的二叉树按“根、左、右”顺序进行先序遍历时,节点值序列恰好等于 voyage。若可以完成,返回所有被翻转节点的值,返回顺序不限;若无法完成,返回只含 -1 的数组。

1 <= n <= 100。

自建示例

在两层分别翻转:

输入:root = [1,2,3,4,5], voyage = [1,3,2,5,4]
输出:[1,2]
解释:先翻转根节点,使节点 3 在节点 2 之前访问;再翻转节点 2,使其孩子访问顺序变为 5、4。

目标序列首项不是根节点:

输入:root = [1,2,3], voyage = [2,1,3]
输出:[-1]
解释:任何翻转都不会改变先序遍历的第一项必须是根节点 1,因此无法匹配以 2 开头的 voyage。