翻转二叉树以匹配先序遍历 图解题解

这道题到底在问什么

输入

root=[50,30,80,20,60], voyage=[50,80,30,20,60]

输出

[50]

输入

root=[50,30], voyage=[30,50]

输出

[-1]

最优解：一步一步想明白

1. 3记住这句话：先比当前值，再看左孩子对不对得上下一个 voyage，不对就翻转换右子树先走。下面每一帧都在套它。
2. 4原先序 50 30 20 60 80先把局面看清。左边这棵树有 5 个节点：根是 50，它的左孩子 30、右孩子 80；30 下面又挂着左孩子 20、右孩子 60。原树的先序（根左右）是 50 30 20 60 80。可目标 voyage 是 50 80 30 20 60，明显对不上，得靠翻转来纠。
3. 5i=0 从根开始我们用一个指针 i 在 voyage 上从左往右走，初始 i=0，指向第一个值 50。再从根节点开始做先序 DFS：每到一个节点，就拿它的值和 voyage[i] 对一对。指针 i 永远只往前走、不回头。现在出发，先看根 50。
4. 6比较 50 与 voyage[i]=50走到节点 50（紫色）。当前指针 i 指向 voyage 里的 50。先序的第一步永远是看根，所以先判断：节点 50 是不是正好等于 voyage[0]=50？一看就相等，匹配上了。
5. 750 匹配，i→1节点 50 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=1，指向 voyage 里的下一个值 80。接下来这一格，决定了 50 要不要翻转。
6. 8左孩子 30 ? voyage[i]=80节点 50 有左孩子 30（红框）。先序里，匹配完根之后紧跟的应该是某棵子树的开头，而 voyage[1]=80。关键一问：左孩子 30 等于 80 吗？等于就让左子树先走，不等就得翻转让右子树先走。
7. 9记入答案，改先右后左左孩子 30 并不等于 voyage 要的 80。原样走左子树会立刻对不上，唯一的补救就是翻转节点 50：把它记进答案，并改成「先走右子树、再走左子树」。50 标成翻转色。这样右子树的开头就有机会接上 80 了。
8. 10比较 80 与 voyage[i]=80走到节点 80（紫色）。当前指针 i 指向 voyage 里的 80。先序的第一步永远是看根，所以先判断：节点 80 是不是正好等于 voyage[1]=80？一看就相等，匹配上了。
9. 1180 匹配，i→2节点 80 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=2，指向 voyage 里的下一个值 30。接下来这一格，决定了 80 要不要翻转。
10. 1280 是叶子，本枝走完节点 80 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
11. 13比较 30 与 voyage[i]=30走到节点 30（紫色）。当前指针 i 指向 voyage 里的 30。先序的第一步永远是看根，所以先判断：节点 30 是不是正好等于 voyage[2]=30？一看就相等，匹配上了。
12. 1430 匹配，i→3节点 30 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=3，指向 voyage 里的下一个值 20。接下来这一格，决定了 30 要不要翻转。
13. 15左孩子 20 ? voyage[i]=20节点 30 有左孩子 20（红框）。先序里，匹配完根之后紧跟的应该是某棵子树的开头，而 voyage[3]=20。关键一问：左孩子 20 等于 20 吗？等于就让左子树先走，不等就得翻转让右子树先走。
14. 16左孩子对得上，先左后右左孩子 20 正好等于 voyage 当前要的 20，说明左子树本来就该排在前面，不用翻转 30。按先序原样「先左子树、再右子树」继续往下走。
15. 17比较 20 与 voyage[i]=20走到节点 20（紫色）。当前指针 i 指向 voyage 里的 20。先序的第一步永远是看根，所以先判断：节点 20 是不是正好等于 voyage[3]=20？一看就相等，匹配上了。
16. 1820 匹配，i→4节点 20 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=4，指向 voyage 里的下一个值 60。接下来这一格，决定了 20 要不要翻转。
17. 1920 是叶子，本枝走完节点 20 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
18. 20比较 60 与 voyage[i]=60走到节点 60（紫色）。当前指针 i 指向 voyage 里的 60。先序的第一步永远是看根，所以先判断：节点 60 是不是正好等于 voyage[4]=60？一看就相等，匹配上了。
19. 2160 匹配，i→5节点 60 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=5，已经走到 voyage 末尾了。
20. 2260 是叶子，本枝走完节点 60 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
21. 23答案 = [50]voyage 指针 i 走到了末尾，途中每个节点都和 voyage 对上了，先序成功对齐。整趟只在节点 50 翻转了一次（因为它的左孩子 30 接不上 voyage 要的 80），节点 30 的左孩子 20 恰好对得上所以没翻。最少翻转点就是 [50]，这就是答案。
22. 2450 翻转，30 不翻回放一遍这条主线：根 50 匹配后，左孩子 30 对不上目标的 80，翻转 50，先去右边的 80；80 是叶子；回来走 30，30 匹配后它的左孩子 20 正好对上目标的 20，不翻转，依次走 20、60，全部命中。整套就是「值不对立刻判无解，左孩子接不上就翻转」，每步都被 voyage 唯一逼着走，所以翻得最少。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        def dfs(root):
            nonlocal i, ok
            if root is None or not ok:
                return
            if root.val != voyage[i]:
                ok = False
                return
            i += 1
            if root.left is None or root.left.val == voyage[i]:
                dfs(root.left)
                dfs(root.right)
            else:
                ans.append(root.val)
                dfs(root.right)
                dfs(root.left)

        ans = []
        i = 0
        ok = True
        dfs(root)
        return ans if ok else [-1]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        bool ok = true;
        int i = 0;
        vector<int> ans;
        function<void(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root || !ok) {
                return;
            }
            if (root->val != voyage[i]) {
                ok = false;
                return;
            }
            ++i;
            if (!root->left || root->left->val == voyage[i]) {
                dfs(root->left);
                dfs(root->right);
            } else {
                ans.push_back(root->val);
                dfs(root->right);
                dfs(root->left);
            }
        };
        dfs(root);
        return ok ? ans : vector<int>{-1};
    }
};

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int i;
    private boolean ok;
    private int[] voyage;
    private List<Integer> ans = new ArrayList<>();

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        ok = true;
        dfs(root);
        return ok ? ans : Arrays.asList(-1);
    }

    private void dfs(TreeNode root) {
        if (root == null || !ok) {
            return;
        }
        if (root.val != voyage[i]) {
            ok = false;
            return;
        }
        ++i;
        if (root.left == null || root.left.val == voyage[i]) {
            dfs(root.left);
            dfs(root.right);
        } else {
            ans.add(root.val);
            dfs(root.right);
            dfs(root.left);
        }
    }
}

复杂度

面试官可能追问