Leetcode Challenge: Invert Binary Tree (6/1)

今天是 6/1，也是正式挑战的第一天，果不其然是一道 Easy 的题目：Invert Binary Tree，如下图的解释不能再多了。题目出处是 No. 226 (https://leetcode.com/problems/invert-binary-tree/)

虽然这道题并不难，但是可以有两种方式来做：DFS & BFS，对于这两个还不是很知道是什么的，可以先去参考网路上的解释。以这题来说， DFS 比较直觉，因为是用递迴的方式 (一个一个 Branch 处理)，而 BFS 则是需要一个 Queue，在过程中会把之后需要交换左右子树的节点放入 Queue 中，并且一次处理 Queue 中的一个节点 (先放入的先拿出来处理)，直到 Queue 中所有的节点都处理完为止 (一层一层往下处理)。

Code 的部分：

DFS：就是用递迴

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def invertTree(self, root: TreeNode) -> TreeNode:        if root is None:            return         root.left, root.right = root.right, root.left        self.invertTree(root.left)        self.invertTree(root.right)        return root

BFS：这里可以用 collections 中的 deque，也可以单纯用个 List 来作为 Queue。

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def invertTree(self, root: TreeNode) -> TreeNode:        if root is None:            return        queue = []        queue.append(root)        while len(queue) > 0:            node = queue.pop(0)            node.left, node.right = node.right, node.left            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        return root

时间上 BFS 会比 DFS 稍快，因为可以看到 BFS 只针对真的节点去处理，但是 DFS 会在进到 function 中才知道这个节点是真的节点还是 None ，所以会多花一些时间。空间上 BFS 最糟就是 Tree 的最大宽度，而 DFS 则是 Tree 的深度，因为要记录 Call Stack。

最后讲讲有趣的事，这个问题似乎源自于 Homebrew 的作者去 Google 面试的时候不会做这题被呛：

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

所以大家把这题学会了，你就有机会比大神更神了 (误

欢迎追蹤我的 Medium 啰！
https://medium.com/@ryanyang1221