the5fire的技术博客

关注python、vim、linux、web开发和互联网--life is short, we need python.


请问你能徒手反转二叉树吗

作者:the5fire | 标签:       | 发布:2016-06-05 8:11 a.m. | 阅读量: 7778, 7653

请问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)

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

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

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


----EOF-----

扫码关注,或者搜索微信公众号:码农悟凡


其他分类: