Flip binary tree to match preorder traversal

Tree Depth-First Search Binary Tree

51.8% acceptance

Feb 27, 2026

1000

284

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].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn flip_match_voyage(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, voyage: Vec<i32>) -> Vec<i32> {
    let mut flips = Vec::new();
    let mut idx = 0usize;
    let mut failed = false;
    fn dfs(
      node: &Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>,
      voyage: &Vec<i32>,
      idx: &mut usize,
      flips: &mut Vec<i32>,
      failed: &mut bool,
    ) {
      if *failed { return; }
      if let Some(n) = node {
        let mut nb = n.borrow_mut();
        if nb.val != voyage[*idx] { *failed = true; return; }
        *idx += 1;
        // Check if we need to flip
        let need_flip = nb.left.is_some()
          && *idx < voyage.len()
          && nb.left.as_ref().unwrap().borrow().val != voyage[*idx];
        if need_flip {
          flips.push(nb.val);
          let tmp = nb.left.take();
          nb.left = nb.right.take();
          nb.right = tmp;
        }
        let left = nb.left.clone();
        let right = nb.right.clone();
        drop(nb);
        dfs(&left, voyage, idx, flips, failed);
        dfs(&right, voyage, idx, flips, failed);
      }
    }
    dfs(&root, &voyage, &mut idx, &mut flips, &mut failed);
    if failed { vec![-1] } else { flips }
  }
}