# 971. Flip Binary Tree To Match Preorder Traversal

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. `1 <= N <= 100`

``````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/

https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/214216/JavaC%2B%2BPython-DFS-Solution

https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/discuss/214384/JavaC%2B%2BPython-Iterative-Solution-Using-Stack

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation