the5fire

请问the5fire，你能徒手反转二叉树吗？ 答曰：你等着。。。。

::

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
翻译一下就是：Homebrew的作者去Google面试，结论是，Google说：我们90%的工程师都在用你写的Homebrew，但是你竟然不能在白板上徒手反转二叉树，滚蛋吧(这太操蛋了)。

来，我们到leetcode刷题吧: https://leetcode.com/problems/invert-binary-tree#/

Python实现如下::

# coding:utf-8
class TreeNode(object):
    def __init__(self, x, leftNode=None, rightNode=None):
        self.val = x
        self.left = leftNode
        self.right = rightNode

    def __str__(self):
        return str(self.val)


class Solution(object):
    def invert_tree(self, node):
        """
        :type node: TreeNode
        :rtype: TreeNode
        """
        if node:
            node.left, node.right = node.right, node.left
            if node.left:
                node.left = self.invert_tree(node.left)
            if node.right:
                node.right = self.invert_tree(node.right)
        return node


def print_tree(node=None, is_child=False, deep=3):
    if not node and is_child:
        return

    if not is_child:
        print node

    if not node.left and not node.right:
        return

    print "%s> " % node, node.left, node.right
    print_tree(node.left, is_child=True)
    print_tree(node.right, is_child=True)


if __name__ == '__main__':
    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(7, TreeNode(6), TreeNode(9))
    )

    print_tree(root)
    print '====='
    solution = Solution()
    invert_node = solution.invert_tree(root)
    print_tree(invert_node)

如果你把这个问题作为面试题的话，应聘者写完之后，还可以继续问如下两个问题：

• 你能写一个函数，用来输出二叉树吗，输出成图上的那个样子?
• 你能把二叉树合并成有序排列的数组吗？

不过在我有限的几年工作中确实没用到过类似的算法，或许用过也忘记了，所以面试的时候问这个感觉没多大用。没事经常刷题的自然会做，平时大部分工作都是业务开发的话，遇到这个那就得靠临场反应了。