【二叉树】翻转二叉树以匹配先序遍历

0x00 题目

给你一棵二叉树的根节点 ​

​root​

​​ 树中有 ​

​n​

​ 个节点

每个节点都有一个不同于其他节点

且处于 ​

​1​

​ 到 ​

​n​

​ 之间的值

另给你一个由 ​

​n​

​​ 个值

组成的行程序列 ​​

​voyage​

​​ 表示预期的二叉树 ​

​先序遍历​

​ 结果

通过交换节点的左右子树

可以 ​​

​翻转​

​ 该二叉树中的任意节点

请翻转 ​

​最少​

​​ 的树中节点

使二叉树的 ​​

​先序遍历​

​​ 与预期的遍历行程 ​

​voyage​

​ 相匹配

如果可以，则返回 ​

​翻转的​

​​ 所有节点的值的列表

你可以按任何顺序返回答案

如果不能，则返回列表 ​​

​[-1]​

​

0x01 思路

因为 ​

​voyage​

​​ 是一个​

​前序​

​​遍历的结果

所以对二叉树进行​​

​前序​

​​遍历

节点为​​

​空​

​​，​

​无​

​​需匹配，那就是​

​匹配​

​​ 节点​

​值​

​不相等时，​

​不​

​匹配

递归子节点，进行相同操作

看​

​是否​

​需要翻转

0x02 解法

语言：​

​Swift​

​

树节点：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func flipMatchVoyage(_ root: TreeNode?, _ voyage: [Int]) -> [Int] {
    var index = 0
    var res: [Int] = []
    
    func dfs(_ root: TreeNode?) -> Bool {
        guard let r = root else { return false }
        // 值不相等，不匹配
        if r.val != voyage[index] { return false }
        
        //索引
        index += 1
        
        // 遍历左右子树
        if dfs(r.left) && dfs(r.right) {
            return true
        }
        
        if dfs(r.right) && dfs(r.left) {
            // 有翻转，添加节点
            res.append(r.val)
            return true
        }
        
        return false
    }
    
    let b = dfs(root)
    if b {
        return res
    }
    
    return [-1]
}      

0x03 我的作品