欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【树-简单】226. 翻转二叉树

程序员文章站 2022-03-03 10:12:36
...

题目
翻转一棵二叉树。

示例:

输入:

 4

/
2 7
/ \ /
1 3 6 9

输出:

 4

/
7 2
/ \ /
9 6 3 1

备注:
这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

【代码】
【方法1:广度优先】
【树-简单】226. 翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root or (not root.left and not root.right): 
            return root
        que=[root]
        while que:
            node=que.pop(0)
            tmp=node.left
            node.left=node.right
            node.right=tmp
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)
        return root

【方法2:深度优先】
【树-简单】226. 翻转二叉树

class Solution:   
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root or (not root.left and not root.right): 
            return root
        tmp=root.left
        root.left=root.right
        root.right=tmp
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
相关标签: 刷题 # leetcode