【二叉樹】翻轉二叉樹以比對先序周遊

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