0971. Flip Binary Tree To Match Preorder Traversal¶
题目信息¶
- 题号:
0971
- 难度:
Medium
- 主题:
二叉树、先序遍历、左右子树翻转
- 原题:
- 重点:
在节点上翻转会交换其左右子树;需要用最少翻转使最终先序遍历等于
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。