# 971. Flip Binary Tree To Match Preorder Traversal¶

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector flipMatchVoyage(TreeNode* root, vector& voyage) { vector ans; dfs(root, 0, voyage, ans); return ans; } private: void dfs(TreeNode* root, int&& i, const vector& voyage, vector& ans) { if (root == nullptr) return; if (root->val != voyage[i++]) { ans.clear(); ans.push_back(-1); return; } if (i < voyage.size() && root->left && root->left->val != voyage[i]) { // Flip the root. ans.push_back(root->val); dfs(root->right, move(i), voyage, ans); dfs(root->left, move(i), voyage, ans); } else { dfs(root->left, move(i), voyage, ans); dfs(root->right, move(i), voyage, ans); } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public List flipMatchVoyage(TreeNode root, int[] voyage) { List ans = new ArrayList<>(); dfs(root, voyage, ans); return ans; } private int i = 0; private void dfs(TreeNode root, int[] voyage, List ans) { if (root == null) return; if (root.val != voyage[i++]) { ans.clear(); ans.add(-1); return; } if (i < voyage.length && root.left != null && root.left.val != voyage[i]) { // Flip the root. ans.add(root.val); dfs(root.right, voyage, ans); dfs(root.left, voyage, ans); } else { dfs(root.left, voyage, ans); dfs(root.right, voyage, ans); } } }