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.
Consider the sequence of N values reported by a preorder traversal starting from the root. Call such a sequence of N values the voyage of the tree.
(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)
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].
Example 1:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Example 2:
Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Example 3:
Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Note:
1 <= N <= 100
这道题给了一棵二叉树，说是我们可以调换任意结点的左右子结点，又给了一个数组，说是按照先序遍历二叉树得到的结点值组成的。现在问能否通过最少的调换操作，使得给定的二叉树经过先序遍历得到的结点值数组和给定的数组相同，可以的话返回需要调换操作的结点值，否则返回 -1。遇到二叉树的问题，十有八九都是递归来做的，这道题也不例外，而且又是先序遍历，妥妥的递归啊。难点在于如何在递归的过程中把问题解决了，由于我们需要在递归的过程中就和给定数组进行比较，所以 voyage 数组是要在递归数组中的，这样就需要一个子函数进行递归调用，而且还要知道当前对比到哪个位置了，需要一个坐标变量传入，同时当然还要传入结果数组 res。同时这个递归函数需要返回一个布尔值，因为有可能是无法生成跟给定数组一样的顺序的。在递归函数中，若当前结点不存在，直接返回 true。若当前结点值不等于数组中的对应位置的值，直接返回 false，因为此时只能调换子结点的位置，当前结点的位置不会改变。否则此时看若左子结点存在，且左子结点值不等于数组中对应位置的值，此时应该尝试进行翻转，先将当前结点值存入结果 res 中，然后先对右子结点调用递归函数，之后再对左子结点调用递归函数，这样就相当于完成了调换左右子结点的操作。否则就按原顺序分别对左右子结点调用递归函数即可，最终在主函数中对于递归函数的返回值需要做个判断，若为 true，则返回 res，否则返回一个只有 -1 的数组，参见代码如下：
class Solution {
public:
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
vector<int> res;
int i = 0;
return helper(root, voyage, i, res) ? res : vector<int>{-1};
}
bool helper(TreeNode* node, vector<int>& voyage, int& i, vector<int>& res) {
if (!node) return true;
if (node->val != voyage[i++]) return false;
if (node->left && node->left->val != voyage[i]) {
res.push_back(node->val);
return helper(node->right, voyage, i, res) && helper(node->left, voyage, i, res);
}
return helper(node->left, voyage, i, res) && helper(node->right, voyage, i, res);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/971
参考资料：
https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
