Medium

题目描述

给你一棵有 n 个节点的二叉树的根节点 root，其中每个节点都有一个从 1 到 n 的唯一值。另外给你一个由 n 个值组成的序列 voyage，这是所期望的二叉树先序遍历结果。

通过交换节点的左右子树，可以翻转该二叉树中的任意节点。例如，翻转节点 1 的效果如下：

翻转最少的节点，使二叉树的先序遍历与 voyage 匹配。

返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。如果不能通过翻转节点使得二叉树的先序遍历与 voyage 匹配，则返回列表 [-1]。

示例 1：

输入：root = [1,2], voyage = [2,1]
输出：[-1]
解释：翻转任何节点都无法令先序遍历匹配 voyage。

示例 2：

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
解释：翻转节点 1 交换了节点 2 和 3，这样先序遍历就和 voyage 匹配了。

示例 3：

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
解释：二叉树已经与 voyage 匹配，因此不需要翻转任何节点。

提示：

  • 树中的节点数目为 n
  • n == voyage.length
  • 1 <= n <= 100
  • 1 <= Node.val, voyage[i] <= n
  • 树中的所有值都是唯一的
  • voyage 中的所有值都是唯一的

解题思路

这道题的核心思路是使用深度优先搜索（DFS）来模拟先序遍历过程，并在必要时翻转节点。

解题思路：

  1. 匹配策略：在DFS过程中，我们维护一个指针来跟踪当前应该匹配的 voyage 中的位置。

  2. 节点值验证：对于当前访问的节点，首先检查其值是否与 voyage[index] 相等，如果不相等则说明无法匹配，返回 [-1]。

  3. 子节点处理：如果当前节点有左右子节点，我们需要决定是否翻转：

    • 如果左子节点的值等于 voyage[index+1]，按原顺序遍历（先左后右）
    • 如果右子节点的值等于 voyage[index+1]，需要翻转当前节点（先右后左），并记录翻转的节点值
    • 如果都不匹配，说明无法通过翻转达到目标序列

  4. 递归遍历：根据是否翻转的决定，递归地处理左右子树。

这种方法的优势是能够在一次遍历中确定最少的翻转次数，时间复杂度为O(n)。

代码实现

class Solution {
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        vector<int> flipped;
        int index = 0;
        
        function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
            if (!node) return true;
            
            if (node->val != voyage[index++]) {
                return false;
            }
            
            if (node->left && node->left->val != voyage[index]) {
                flipped.push_back(node->val);
                return dfs(node->right) && dfs(node->left);
            }
            
            return dfs(node->left) && dfs(node->right);
        };
        
        return dfs(root) ? flipped : vector<int>{-1};
    }
};

class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        flipped = []
        self.index = 0
        
        def dfs(node):
            if not node:
                return True
            
            if node.val != voyage[self.index]:
                return False
            
            self.index += 1
            
            if (node.left and self.index < len(voyage) and 
                node.left.val != voyage[self.index]):
                flipped.append(node.val)
                return dfs(node.right) and dfs(node.left)
            
            return dfs(node.left) and dfs(node.right)
        
        return flipped if dfs(root) else [-1]

public class Solution {
    private IList<int> flipped;
    private int index;
    
    public IList<int> FlipMatchVoyage(TreeNode root, int[] voyage) {
        flipped = new List<int>();
        index = 0;
        
        return DFS(root, voyage) ? flipped : new List<int> { -1 };
    }
    
    private bool DFS(TreeNode node, int[] voyage) {
        if (node == null) return true;
        
        if (node.val != voyage[index++]) {
            return false;
        }
        
        if (node.left != null && index < voyage.Length && 
            node.left.val != voyage[index]) {
            flipped.Add(node.val);
            return DFS(node.right, voyage) && DFS(node.left, voyage);
        }
        
        return DFS(node.left, voyage) && DFS(node.right, voyage);
    }
}

var flipMatchVoyage = function(root, voyage) {
    let flipped = [];
    let index = 0;
    
    function dfs(node) {
        if (!node) return true;
        
        if (node.val !== voyage[index++]) {
            return false;
        }
        
        if (node.left && index < voyage.length && 
            node.left.val !== voyage[index]) {
            flipped.push(node.val);
            return dfs(node.right) && dfs(node.left);
        }
        
        return dfs(node.left) && dfs(node.right);
    }
    
    return dfs(root) ? flipped : [-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次，其中 n 是节点数量
空间复杂度O(h)递归调用栈的深度等于树的高度 h，最坏情况下为 O(n)