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

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 我的作品

欢迎体验我的作品之一：小五笔
五笔学习好帮手
App Store 搜索即可~

---