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``。 自建示例 -------- 在两层分别翻转: .. code-block:: text 输入:root = [1,2,3,4,5], voyage = [1,3,2,5,4] 输出:[1,2] 解释:先翻转根节点,使节点 3 在节点 2 之前访问;再翻转节点 2,使其孩子访问顺序变为 5、4。 目标序列首项不是根节点: .. code-block:: text 输入:root = [1,2,3], voyage = [2,1,3] 输出:[-1] 解释:任何翻转都不会改变先序遍历的第一项必须是根节点 1,因此无法匹配以 2 开头的 voyage。