明星程式員被Google挂掉的故事

首先要提一個軟體Homebrew

Homebrew可能是Mac上最好用的包管理器, 地位相當于Ubuntu的apt, 也相當于指令行版的AppStore

Homebrew

brew

Max Howell是Homebrew的作者, 某天去google面試, 面試官出了一道反轉二叉樹的題目, 然而Max Howell沒答上來, 最後, 就成為了一段佳話.

反轉二叉樹

• Google面試官：Max Howell來我大Google，這是好事情，一定要留下他! 不能出太難的題，也不能太直白; 是以題目既要簡單又要逼格，樹結構應該是比較合适了，樹裡最常見的就是二叉樹，考的最多的也是二叉搜尋樹了, 那就反轉二叉樹了吧, 哈哈, 我真的太tm機智了！
• Max Howell: 老兄，你這讓我很尴尬呀，今天的事兒就算了，求不說...

哈哈，挖坑不填不是我的風格，python版解題源碼奉上！

class Node(object):
    def __init__(self, value = None):
        self.value = value
        self.left = None
        self.right = None



class Tree(object):
    def __init__(self):
        self.root = Node()
        self.queue = []
        pass

    def add(self, value):
        # 建立一個節點
        tmp_node = Node(value)
        # 如果根節點為空, 則添加根節點
        if len(self.queue) == 0:
            self.root = tmp_node
            self.queue.append(tmp_node)
        # 如果根節點不為空
        else:
            # 擷取目前子樹未滿的節點(目前臨時父節點)
            nowRoot = self.queue[0]
            # 如果臨時父節點左子樹為空
            if nowRoot.left == None:
                nowRoot.left = tmp_node
                self.queue.append(tmp_node)
            # 如果臨時父節點右子樹為空
            else:
                nowRoot.right = tmp_node
                self.queue.append(tmp_node)
                # 從隊列清除父節點(這個父節點現在已經滿了)
                self.queue.pop(0)
    # 中序周遊
    def recursion_lvr(self, root):
        # 如果節點為空, 則傳回
        if not root:
            return
        self.recursion_lvr(root.left)
        print(root.value)
        self.recursion_lvr(root.right)

    # 反轉二叉樹(HomeBrew的作者被坑的題目)
    def reverse_tree(self, root):
        if not root:
            return
        # 擷取目前左右子樹的根節點
        tmp_left_node = root.left
        tmp_right_node = root.right

        # 反轉二叉樹的左右子樹
        root.left = tmp_right_node
        root.right = tmp_left_node

        # 将左右子樹加入新的序列
        self.reverse_tree(root.left)
        self.reverse_tree(root.right)



def main():
    tree = Tree()
    for i in range(1,8):
        tree.add(i)

    tree.recursion_lvr(tree.root);

    tree.reverse_tree(tree.root)


    print("反轉之後的結果:")
    tree.recursion_lvr(tree.root);


if __name__ == '__main__':
    main()

           

綜上所述, 算法的确很重要......