[binary tree] flip the binary tree to match the preorder traversal

0x00 subject

Give you the root node of a binary tree root
There is... In the tree n Nodes
Each node has a different node
And in 1 To n Between the value of the

Give you another one by n It's worth
Make up the journey sequence voyage
Represents the expected binary tree The first sequence traversal result

By exchanging the left and right subtrees of nodes
Sure Flip Any node in the binary tree

Please flip least Nodes in the tree
Make the of a binary tree The first sequence traversal With the expected traversal travel voyage Match

If possible , Then return to Flipped List of values of all nodes
You can return the answers in any order
If not , Then return to the list [-1]

---

0x01 Ideas

because voyage It's a Before the order The result of traversal
So we do a binary tree Before the order Traverse
The node is empty , nothing Need to match , That's it matching
node value When they are not equal , No matching
Recursive child node , Do the same
see whether Need to flip

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

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 }
        //  Value inequality , Mismatch 
        if r.val != voyage[index] { return false }
        
        // Indexes 
        index += 1
        
        //  Traverse the left and right subtrees 
        if dfs(r.left) && dfs(r.right) {
            return true
        }
        
        if dfs(r.right) && dfs(r.left) {
            //  There's a flip , Add a node 
            res.append(r.val)
            return true
        }
        
        return false
    }
    
    let b = dfs(root)
    if b {
        return res
    }
    
    return [-1]
}

---

0x03 My work

Welcome to experience one of my works ： Small five strokes
Wubi learning is a good helper
App Store Search ~

---