mute_tree.cc

void mutate_binary_tree(const shared_ptr<BinaryTree> &root) {
    if (!root) {
        return;
    }
    mute_dfs_post_order(root);
    shared_ptr<BinaryTree> n = root;
    while (n->left) {
        auto current = n;
        auto next = current->left;
        next = get_right_most(next);
        while (current->right && current->right->left) {
            next->right = current->right->left;
            next = get_right_most(next);
            current->right->left = nullptr;
            current = current->right;
        }
        n = n->left;
    }
}

shared_ptr<BinaryTree> get_right_most(shared_ptr<BinaryTree> n) {
    while (n && n->right) {
        n = n->right;
    }
    return n;
}

void mutate_dfs_post_order(const shared_ptr<BinaryTree> &n) {
    if (!n) {
        return;
    }
    
    mutate_dfs_post_order(n->left);
    mutate_dfs_post_order(n->right);
    if (n->right) {
        n->left ? n->left->right = n->right : n->left = n->right;
        n->right = nullptr;
    }
}