0971. Flip Binary Tree to Match Preorder Traversal

971. Flip Binary Tree To Match Preorder Traversal#

题目 #

You are given the `root` of a binary tree with `n` nodes, where each node is uniquely assigned a value from `1` to `n`. You are also given a sequence of `n` values `voyage`, which is the desired  pre-order traversal of the binary tree.

Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

Flip the smallest number of nodes so that the pre-order traversal of the tree matches `voyage`.

Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match `voyage`*, return the list* `[-1]`.

Example 1:

``````Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
``````

Example 2:

``````Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
``````

Example 3:

``````Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.
``````

Constraints:

• The number of nodes in the tree is `n`.
• `n == voyage.length`
• `1 <= n <= 100`
• `1 <= Node.val, voyage[i] <= n`
• All the values in the tree are unique.
• All the values in `voyage` are unique.

解题思路 #

• 题目要求翻转最少树中节点，利用贪心的思想，应该从根节点开始从上往下依次翻转，这样翻转的次数是最少的。对树进行深度优先遍历，如果遍历到某一个节点的时候，节点值不能与行程序列匹配，那么答案一定是 [-1]。否则，当下一个期望数字 `voyage[i]` 与即将遍历的子节点的值不同的时候，就要翻转一下当前这个节点的左右子树，继续 DFS。递归结束可能有 2 种情况，一种是找出了所有要翻转的节点，另一种情况是没有需要翻转的，即原树先序遍历的结果与 `voyage` 是完全一致的。

代码 #

``````package leetcode

import (
"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

func flipMatchVoyage(root *TreeNode, voyage []int) []int {
res, index := make([]int, 0, len(voyage)), 0
if travelTree(root, &index, voyage, &res) {
return res
}
return []int{-1}
}

func travelTree(root *TreeNode, index *int, voyage []int, res *[]int) bool {
if root == nil {
return true
}
if root.Val != voyage[*index] {
return false
}
*index++
if root.Left != nil && root.Left.Val != voyage[*index] {
*res = append(*res, root.Val)
return travelTree(root.Right, index, voyage, res) && travelTree(root.Left, index, voyage, res)
}
return travelTree(root.Left, index, voyage, res) && travelTree(root.Right, index, voyage, res)
}
``````

Apr 8, 2023