971. 翻转二叉树以匹配先序遍历

题目

给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。

另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。

通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：

请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。

如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。

难度：🌟🌟🌟🌟

示例 1：

输入：root = [1,2], voyage = [2,1]
输出：[-1]
解释：翻转节点无法令先序遍历匹配预期行程。

示例 2：

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。

示例 3：

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
解释：先序遍历已经匹配预期行程，所以不需要翻转节点。

提示：

• 树中的节点数目为 n
• n == voyage.length
• 1 <= n <= 100
• 1 <= Node.val, voyage[i] <= n
• 树中的所有值 互不相同
• voyage 中的所有值 互不相同

题解

思路一：
从题意很容易联想到可以使用前序遍历迭代方式，在迭代过程中比较对应位置的节点值和 voyage 中数值的大小。如果相同，则进行下一个节点比较；否则，交换左右节点。
有两个特殊情况需要处理：

1. 栈中没有元素且二叉树节点值和对应 voyage 中的值不相等时，此时翻转节点无法匹配先序遍历行程 voyage；
2. 当节点的左右子树交换后仍然无法和 voyage 中对应值相等，则此时翻转节点无法匹配先序遍历行程 voyage。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
	if root == nil {
		return nil
	}
	var ans []int
	var pos int // 记录遍历的节点对应 voyage 的位置
	var stack []*TreeNode
	diffMap := make(map[int]bool)
	for root != nil || len(stack) > 0 {
		if len(stack) == 0 && root.Val != voyage[pos] {
			return []int{-1}
		}
		if root != nil {
			if root.Val == voyage[pos] {
				// 当前节点和先序遍历节点相同，则跳到下一节点
				stack = append(stack, root)
				root = root.Left
				pos++
			} else {
				// 记录不相同的元素
				if diffMap[root.Val] { // 此时不管如何交换左右节点都不可能相等
					return []int{-1}
				} else {
					diffMap[root.Val] = true
				}
				// 按 root 进行翻转
				root = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				pos--
				// 记录翻转节点
				ans = append(ans, root.Val)
				tmp := root.Left
				root.Left = root.Right
				root.Right = tmp
			}
		} else {
			// 弹出栈顶元素
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			root = root.Right
		}
	}
	return ans
}