美文网首页
难倒Homebrew发明人的翻转二叉树到底有多简单?

难倒Homebrew发明人的翻转二叉树到底有多简单?

作者: 泰克尼客 | 来源:发表于2021-04-25 10:59 被阅读0次

    什么是翻转二叉树

    大家都知道Homebrew发明人Max Howell面试谷歌时,被一道翻转二叉树的题目给难倒了。那么什么是翻转二叉树呢?看看下图就明白了。


    翻转二叉树.png

    简单地说,就是对于一棵二叉树及其所有子树,交换其左右位置。

    思路

    首先,看到一棵二叉树时,我们不要被庞大的分支结构所吓倒,其实,其基本构成就是根节点左子树右子树这三个元素而已。大多数问题只需要考虑这三者之间的关系就能被解决;
    其次,对于树相关的问题,我们的第一反应是尝试能否通过递归的方法来实现。

    理清了二叉树的基本结构(根节点左子树右子树),并使用递归的思路来思考,自然可以得出下面的递归过程:

    • 让左子树完成翻转
    • 让右子树完成翻转
    • 交换左右子树

    自然就能完成全部的翻转过程了。可以参考下图:

    翻转过程.png
    我们先完成了左子树的翻转,接着完成了右子树的翻转,最后在根节点处交换了左右子树。可以很自然地写出如下的递归代码:
    class Solution:
        def invertTree(self, root: TreeNode) -> TreeNode:
            left = self.invertTree(root.left)
            right = self.invertTree(root.right)
            root.left, root.right = right, left
            return root
    

    考虑递归终止条件后的最终代码

    递归相关的代码,最重要的有两点,一是理清递归的思路,也就是上文所述的内容,另一点是递归的终止条件。从上述递归过程可以知道,当根节点为空或者递归到叶子节点时,由于左右子树均为空,那么直接返回就行了。所以为完备性考虑,修正递归代码为:

    class Solution:
        def invertTree(self, root: TreeNode) -> TreeNode:
            if not root:
                return root
            
            left = self.invertTree(root.left)
            right = self.invertTree(root.right)
            root.left, root.right = right, left
            return root
    

    回顾

    树相关的操作,先考虑递归能否实现,所谓的递归过程,也无非是考虑根节点左子树右子树三者之间的关系。最后再考虑一下根节点为空叶子节点的边界情况,那么基本能写个七七八八出来了。好了,这样就可以胜过Max Howell了。狗头滚粗...

    相关文章

      网友评论

          本文标题:难倒Homebrew发明人的翻转二叉树到底有多简单?

          本文链接:https://www.haomeiwen.com/subject/dqtdrltx.html