明星程序员被Google挂掉的故事

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()