#971

Flip Binary Tree To Match Preorder Traversal

specialist · 870 · lc medium +31 · failed · 51.8% accepted · 1,000 likes · top 41%

Description

A binary tree of n uniquely-labeled nodes (values 1 to n) is rooted at root. You may flip (swap children) any node. Return the values of the nodes that must be flipped so the pre-order traversal matches the target sequence voyage, or [-1] if it is impossible.

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.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]: