Leetcode daily question (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.

---

use preorder To traverse the tree , At the same time vayage Contrast , If the value of the left node is the same as voyage If the next value of is equal, the left node is used for the next traversal , If the value of the right node is the same as voyage The next value of is equal , Then use the node on the right to go through the next step . But if you need to traverse with the right node, it proves that the left and right nodes need to be interchanged , So the value of the current node needs to be added to the answer array .

---

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    
    fn rc(root: Option<Rc<RefCell<TreeNode>>>, voyage: &mut Vec<i32>) -> Vec<i32> {
    
        if let Some(node) = root {
    
            let v = voyage.remove(0);
            if node.borrow().val != v {
    
                return vec![-1];
            }
            let left = node.borrow_mut().left.take();
            let right = node.borrow_mut().right.take();
            let left_val = if let Some(l) = &left {
    
                l.borrow().val
            } else {
    
                -1
            };
            let right_val = if let Some(r) = &right {
    
                r.borrow().val
            } else {
    
                -1
            };
            if left_val == -1 && right_val == -1 {
    
                return vec![];
            }
            if left_val == voyage[0] {
    
                let mut l = Solution::rc(left, voyage);
                if l == vec![-1] {
    
                    return vec![-1];
                }
                let mut r = Solution::rc(right, voyage);
                if r == vec![-1] {
    
                    return vec![-1];
                }
                l.append(&mut r);
                return l;
            }
            let mut l = Solution::rc(right, voyage);
            if l == vec![-1] {
    
                return vec![-1];
            }
            let mut r = Solution::rc(left, voyage);
            if r == vec![-1] {
    
                return vec![-1];
            }
            l.append(&mut r);
            if left_val != -1 {
    
                l.push(node.borrow().val);
            }
            return l;
        }
        vec![]
    }
    pub fn flip_match_voyage(
        root: Option<Rc<RefCell<TreeNode>>>,
        mut voyage: Vec<i32>,
    ) -> Vec<i32> {
    
        Solution::rc(root, &mut voyage)
    }
}