【二叉樹】翻轉一棵二叉樹

0x00 題目

給你一棵二叉樹的根節點 ​

​root​

​，翻轉它。

0x01 思路

​

​翻轉​

​​，就是把左、右節點​

​交換​

​​過來。

既然要交換，就不能隻交換​​

​一個​

​​節點。

是以要交換全部，那就得​​

​周遊​

​​

​周遊​

​ 方式有：

​

​深度​

​優先：​

​前序​

​周遊，​

​中序​

​周遊，​

​後序​

​周遊

​

​廣度​

​優先：​

​層序​

​周遊

然而，這裡有一個​

​坑​

​，後面說…

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 invertTree(_ root: TreeNode?) -> TreeNode? {
    // 節點為空，該回頭了
    guard let root = root else { return nil }
    
    // 前序周遊代碼  -> 見下面的具體代碼
    invertTree(root.left)
    // 中序周遊代碼  -> 見下面的具體代碼
    invertTree(root.right)
    // 後序周遊代碼  -> 見下面的具體代碼
    
    return root
}      

具體代碼：

let node = root.left
    root.left = root.right
    root.right = node
    
    // (root.left, root.right) = (root.right, root.left)      

其中，上面所說的​

​坑​

​​，就在​

​中序​

​周遊 的位置

中序周遊順序是：左中右（左節點，根節點，右節點）

左：交換左節點的，​​

​左子​

​​節點與​

​右子​

​​節點

中：交換，左節點換到右邊去了

右：交換，其實是在操作​​

​左​

​​節點

最終，​​

​右​

​​節點沒有進行交換

看！​​

​坑​

​ 就在這裡

func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else {
        return nil
    }
    
    var queue: [TreeNode] = [root]
    while !queue.isEmpty {
        // 用來儲存下一層的節點
        var tmp: [TreeNode] = []

        while !queue.isEmpty {
            let node = queue.removeFirst()
            // 交換
            (node.left, node.right) = (node.right, node.left)

            if let left = node.left {
                tmp.append(left)
            }

            if let right = node.right {
                tmp.append(right
            }
        }

        queue = tmp
    }

    return root
}      

小五筆