题目描述

给定一棵 N 个结点的二叉树，每个结点都有一个不同的值，范围在 {1, ..., N} 中。

一个在二叉树中的结点可以交换左右儿子。

考虑一个 N 个值的序列，表示从根结点开始的先序遍历。称这 N 个值的序列为一棵树的 游历 。

（回忆一个结点的先序遍历，首先报告当前结点的值，然后先序遍历左儿子，然后先序遍历右儿子）

我们的目标是翻转最少次数的结点，使得树的 游历 和我们给定的 游历 一致。

如果你可以做到，返回需要翻转结点的列表，你可以以任何顺序返回答案。

如果你做不到，返回 [-1]。

样例

输入：root = [1,2], voyage = [2,1]
输出：[-1]

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]

注意

• 1 <= N <= 100

算法

(递归) $O(n)$

1. 定义布尔类型的递归，如果当前结点和子树已经不可能和给定的游历顺序匹配，则返回 false；否则返回 true。
2. 当前结点为空，返回 true；如果当前结点的值和给定的游历顺序的下一个值不相等，返回 false；
3. 通过了 2 之后，首先递归左子树和右子树，如果二者返回值都是 true，则返回 true；
4. 如果 3 不成功，则递归右子树和左子树，如果二者返回值都是 true，则答案中记录当前结点，返回 true；
5. 都不成功返回 false;

时间复杂度

• 由于每个结点的值都不同，所以如果答案存在，则每一层都能唯一确定保持原状还是翻转左右子树，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的数组保存答案，递归需要 $O(H)$ 的空间，故总空间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    bool dfs(TreeNode *rt, const vector<int>& voyage, int& cur, vector<int>& ans) {
        if (rt == nullptr)
            return true;

        if (rt -> val != voyage[cur])
            return false;

        cur++;

        if (dfs(rt -> left, voyage, cur, ans) && dfs(rt -> right, voyage, cur, ans))
            return true;

        if (dfs(rt -> right, voyage, cur, ans) && dfs(rt -> left, voyage, cur, ans)) {
            ans.push_back(rt -> val);
            return true;
        }

        return false;
    }

    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        int cur = 0;
        vector<int> ans;

        if (!dfs(root, voyage, cur, ans))
            return {-1};

        return ans;
    }
};