971. Flip Binary Tree To Match Preorder Traversal Medium

1/**
2 * [971] Flip Binary Tree To Match Preorder Traversal
3 *
4 * 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 <a href="https://en.wikipedia.org/wiki/Tree_traversal#Pre-order" target="_blank">pre-order traversal</a> of the binary tree.
5 * 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:
6 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/15/fliptree.jpg" style="width: 400px; height: 187px;" />
7 * Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.
8 * 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].
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2019/01/02/1219-01.png" style="width: 150px; height: 205px;" />
12 * Input: root = [1,2], voyage = [2,1]
13 * Output: [-1]
14 * Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2019/01/02/1219-02.png" style="width: 150px; height: 142px;" />
18 * Input: root = [1,2,3], voyage = [1,3,2]
19 * Output: [1]
20 * Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
21 * Example 3:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2019/01/02/1219-02.png" style="width: 150px; height: 142px;" />
23 * Input: root = [1,2,3], voyage = [1,2,3]
24 * Output: []
25 * Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	The number of nodes in the tree is n.
31 * 	n == voyage.length
32 * 	1 <= n <= 100
33 * 	1 <= Node.val, voyage[i] <= n
34 * 	All the values in the tree are unique.
35 * 	All the values in voyage are unique.
36 * 
37 */
38pub struct Solution {}
39use crate::util::tree::{TreeNode, to_tree};
40
41// problem: https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/
42// discuss: https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46// Definition for a binary tree node.
47// #[derive(Debug, PartialEq, Eq)]
48// pub struct TreeNode {
49//   pub val: i32,
50//   pub left: Option<Rc<RefCell<TreeNode>>>,
51//   pub right: Option<Rc<RefCell<TreeNode>>>,
52// }
53// 
54// impl TreeNode {
55//   #[inline]
56//   pub fn new(val: i32) -> Self {
57//     TreeNode {
58//       val,
59//       left: None,
60//       right: None
61//     }
62//   }
63// }
64use std::rc::Rc;
65use std::cell::RefCell;
66impl Solution {
67    pub fn flip_match_voyage(root: Option<Rc<RefCell<TreeNode>>>, voyage: Vec<i32>) -> Vec<i32> {
68        vec![]
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_971() {
80    }
81}
82