【树-简单】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:广度优先】
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:深度优先】
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】226. 翻转二叉树