void core(string &str)
{
    int len = str.size(), cur, right;
    cur = right = len - 1;

    for (; cur >= 0; cur--)
    {
        if (str[cur] == '#')
            continue;
        else
        {
            if (cur != right)

                swap(str[cur], str[right]);

            right--;
        }
    }
}

struct TreeNode {
    int val;     
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;

    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);

    if (!left && !right)
        return root;

    if (!right) return right;
    else return left;
}

bool dfs(TreeNode *root, TreeNode *p, TreeNode *q, vector<TreeNode*> &path, vector<vector<TreeNode*>> &res)
{
    if (!root) return false;

    if (root == p || root == q)
    {
        path.push_back(root);
        res.push_back(path);
        path.pop_back();
        return true;
    }

    path.push_back(root);
    if (dfs(root->left, p, q, path, res)) return true;
    if (dfs(root->right, p, q, path, res)) return true;
    path.pop_back();

    return false;
}

vector<TreeNode*> findPath(TreeNode* root, TreeNode* p, TreeNode* q)
{
    TreeNode *ancestor = lowestCommonAncestor(root, p, q);
    vector<TreeNode*> left_path, right_path;
    vector<vector<TreeNode*>> res;
    dfs(ancestor->left, p, q, left_path, res);
    dfs(ancestor->right, p, q, right_path, res);
    vector<TreeNode*> path;

    for (int i = res[0].size() - 1; i >= 0; i--)
        path.push_back(res[0][i]);

    path.push_back(ancestor);

    for (int i = 0; i < (int)res[1].size() - 1; i++)
        path.push_back(res[1][i]);
    
    return path;
}