971. Flip Binary Tree To Match Preorder Traversal #

Problem #

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.

Problem Summary #

Given the root node root of a binary tree, the tree has n nodes, and each node has a value that is different from all other nodes and is between 1 and n. You are also given a sequence voyage consisting of n values, representing the expected preorder traversal result of the binary tree. By swapping a node’s left and right subtrees, you can flip any node in the binary tree. Please flip the fewest nodes in the tree so that the binary tree’s preorder traversal matches the expected traversal voyage. If possible, return the list of values of all flipped nodes. You may return the answer in any order. If it is not possible, return the list [-1].

Solution Approach #

• The problem asks us to flip the fewest nodes in the tree. Using a greedy idea, we should start from the root node and flip from top to bottom in order, so the number of flips is minimized. Perform a depth-first traversal of the tree. If, when visiting a certain node, the node value cannot match the voyage sequence, then the answer must be [-1]. Otherwise, when the next expected number voyage[i] differs from the value of the child node that is about to be traversed, flip the current node’s left and right subtrees and continue DFS. When the recursion ends, there may be 2 cases: one is that all nodes to be flipped have been found; the other is that no flips are needed, meaning the preorder traversal result of the original tree is completely consistent with voyage.

Code #

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)
}