给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。
（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）
我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。
示例 1：
输入：root = [1,2], voyage = [2,1] 输出：[-1]
示例 2：
输入：root = [1,2,3], voyage = [1,3,2] 输出：[1]
示例 3：
输入：root = [1,2,3], voyage = [1,2,3] 输出：[]
提示：
1 <= N <= 100
题目标签：Tree / Depth-first Search
题目链接：LeetCode / LeetCode中国
| Language | Runtime | Memory |
|---|---|---|
| cpp | 4 ms | 1.2 MB |
/**
* 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:
vector<TreeNode*> pre;
bool flag = true;
vector<int> res;
void preorder(TreeNode* node) {
if (!node) return;
pre.push_back(node);
preorder(node->left);
preorder(node->right);
}
void dfs(TreeNode* node, vector<int>& voy, int vst, int ved, int pst, int ped) {
// cout << "[In] " << vst << ", " << ved << ", " << pst << ", " << ped << endl;
if (!node) return;
if (!flag) return;
if (node->val != voy[vst]) {
flag = false;
// cout << "a" << endl;
return;
}
if (ved - vst != ped - pst) {
flag = false;
// cout << "b" << endl;
return;
}
if (ved - vst == 1 && ped - pst == 1) {
// cout << "only root" << endl;
return;
} else {
if (ved - vst == 1) {
flag = false;
// cout << "c" << endl;
return;
}
if (ped - pst == 1) {
// cout << "d" << endl;
flag = false;
return;
}
}
if (node->left && node->right) {
if (node->left->val == voy[vst+1]) {
int t = node->right->val;
int x = 0, y = 0;
for (int i=vst; i<ved; ++i) {
if (voy[i] == t) {
y = i;
break;
}
}
for (int i=pst; i<ped; ++i) {
if (pre[i]->val == t) {
x = i;
break;
}
}
if (x - pst == y - vst) {
dfs(node->left, voy, vst+1, y, pst+1, x);
dfs(node->right, voy, y, ved, x, ped);
return;
}
}
} else {
if (node->left) {
if (node->left->val == voy[vst+1]) {
dfs(node->left, voy, vst+1, ved, pst+1, ped);
return;
} else {
flag = false;
return;
}
}
if (node->right) {
if (node->right->val == voy[vst+1]) {
dfs(node->right, voy, vst+1, ved, pst+1, ped);
return;
} else {
flag = false;
return;
}
}
// cout << "leaf node!" << endl;
return;
}
int x = 0;
for (int i=pst; i<ped; ++i) {
if (pre[i]->val == voy[vst+1]) {
x = i;
break;
}
}
int y = 0;
for (int i=vst; i<ved; ++i) {
if (voy[i] == pre[pst+1]->val) {
y = i;
break;
}
}
// cout << "x: " << x << " y: " << y << endl;
if (x - pst - 1 == ved - y && ped - x == y - vst - 1) {
// cout << "push: " << voy[vst] << endl;
res.push_back(voy[vst]);
dfs(node->left, voy, y, ved, pst+1, x);
dfs(node->right, voy, vst+1, y, x, ped);
} else {
// cout << "e" << endl;
flag = false;
return;
}
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
if (!root || voyage.size() == 0) {
res.push_back(-1);
return res;
}
preorder(root);
// for (auto i : pre) cout << i->val << " ";
// cout << endl;
dfs(root, voyage, 0, pre.size(), 0, voyage.size());
if (!flag) {
res.clear();
res.push_back(-1);
return res;
}
return res;
}
};