Flipping Binary Trees to Match Preorder Traversal

Given a binary tree with N nodes, each node has a different value from 1, …, N. A node in this binary tree can be flipped by swapping the left child and the right child of that node. Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyage we are given. If we can do so, then return a list of the values of all nodes flipped. You may return the answer in any order. If we cannot do so, then return the list [-1].

Approach

Tree depth-first search. The root node must first match the value at index i in the array. The traversal returns a boolean indicating success. Each DFS call increments i. No flip means continue traversing. When we need to flip, we must check that both children exist first. My initial solution missed this edge case.

Optimal Solution

class Solution {
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        if (flip(root, voyage)) return res;
        // If failed to flip, clear exist element in res
        res.clear();
        res.push_back(-1);
        return res;
    }
    
    bool flip(TreeNode* root, vector<int>& v) {
        if (root == NULL) return true;
        if (root->val != v[i]) return false;
        
        ++i;
        if (root->left && root->left->val == v[i]) {
            return flip(root->left, v) && flip(root->right, v);
        } else if (root->right && root->right->val == v[i]) {
            // Flip needs two children not null ?? 题目划线部分重点！！
            if (root->left)
                res.push_back(root->val);
            return flip(root->right, v) && flip(root->left, v);
        }
        // It may no children
        return !root->left && !root->right;
    }
    
    vector<int> res;
    int i=0;
};

Key Insight

The preorder traversal array generation depends on whether we visit left or right subtrees first. So flipping problems just swap the recursion order and add operations that satisfy the problem requirements.

#tree