[LeetCode] 971. Flip Binary Tree To Match Preorder Traversal

[grandyang]

You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.

Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.

Return *a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage , return the list *[-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.

Constraints:

• The number of nodes in the tree is n.
• n == voyage.length
• 1 <= n <= 100
• 1 <= Node.val, voyage[i] <= n
• All the values in the tree are unique.
• All the values in voyage are unique.

这道题给了一棵二叉树，说是我们可以调换任意结点的左右子结点，又给了一个数组，说是按照先序遍历二叉树得到的结点值组成的。现在问能否通过最少的调换操作，使得给定的二叉树经过先序遍历得到的结点值数组和给定的数组相同，可以的话返回需要调换操作的结点值，否则返回 -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 同步地址:

#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 打赏

---|---