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

先序要变成 voyage，能翻哪些节点

先序遍历，也就是先访问自己、再左子树、再右子树。翻转一个节点就是把它左右子树对调，先序里这两棵子树的先后随之互换。题目要用最少翻转让整棵树的先序等于目标序列 voyage，做不到返回 [-1]。题面例子 root=[50,30,80,20,60]、voyage=[50,80,30,20,60] 返回 [50]；root=[50,30]、voyage=[30,50] 返回 [-1]。

把每种翻法都试一遍，为什么撑不住

每个节点都能翻或不翻，n 个节点就有 2 的 n 次方种翻法。逐一翻出整棵树再算先序去对 voyage，节点稍多就是天文数字，还要挑翻得最少的，稍大的树根本跑不完。

每个节点翻不翻，voyage 早就定死了

先序永远先落在根上。某节点匹配完自己、指针挪一格后，先序接下来要的 voyage[i] 就是紧跟的那棵子树开头。若该节点左孩子值正好等于 voyage[i]，左子树本就该排前面、不能翻；若对不上，只能翻转让右子树先走去接。两种各只有一个动作、没有可翻可不翻的余地，照做次数天然最少；左右孩子都接不上就判无解，主线走前序 DFS。

一趟前序 DFS，每到一个节点做三件事

用全局指针 i 指着 voyage，从 0 起、只增不减。进入节点先拿它的值和 voyage[i] 比：不等就把 ok 标失败、返回，就此无解。相等则 i 加一，再看左孩子——左孩子为空、或值等于此刻的 voyage[i]，就先递归左子树、再递归右；否则把节点值追加进答案数组 ans，改成先递归右、再递归左。走完 ok 仍为真返回 ans，否则返回 [-1]。

拿题面这棵五节点的树，逐个节点定翻不翻

root=[50,30,80,20,60]：根 50 挂左 30、右 80，30 再挂左 20、右 60；voyage=[50,80,30,20,60]。i 从 0 进 50，50 对上 voyage[0]，i 变 1。50 的左孩子 30 不等于 voyage[1]=80，翻转：50 记进 ans，改先走右子树。到 80 对上 voyage[1]，i 变 2，叶子返回。回到 30 对上 voyage[2]，i 变 3，左孩子 20 等于 voyage[3]=20，不翻走左。到 20 对上 voyage[3]，i 变 4。再到 60 对上 voyage[4]，i 变 5 到末尾。只翻 50 一次，返回 [50]。

单节点、根就对不上，各返回什么

每个节点在 DFS 里只访问一次，节点内比较、记录都是常数功夫，时间 O(n)。空间只花在递归栈上，层数跟着树高 h 走，越均衡越近 O(log n)、歪成链时到 O(n)。边界上，只有一个节点时根一匹配就返回空数组 []；根值和 voyage[0] 一开始就对不上就返回 [-1]，例二 root=[50,30]、voyage=[30,50] 正是根 50 接不住 30。两处暗坑：判左孩子比的是 i 自增后的 voyage[i]，写成 voyage[i+1] 会挪错一格；翻转时只记答案却忘把递归改成先右后左，等于白记。

Python

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]

C++

#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};
    }
};

Java

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);
        }
    }
}