题目描述:
Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9
to
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
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.
题目大意:
翻转一棵二叉树。
测试样例见题目描述。
花絮:
这道题目的灵感来自于Max Howell的推特原文:
Google:我们90%的工程师在用你写的软件(Homebrew),但你竟然不会在白板上翻转一棵二叉树,所以滚吧。
解题思路:
水题,递归或者队列迭代均可。
Python代码(递归版本):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {TreeNode}
def invertTree(self, root):
if root is None:
return None
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
Python代码(迭代版本):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {TreeNode}
def invertTree(self, root):
if root is None:
return None
queue = [root]
while queue:
front = queue.pop(0)
if front.left:
queue.append(front.left)
if front.right:
queue.append(front.right)
front.left, front.right = front.right, front.left
return root
本文链接:http://bookshadow.com/weblog/2015/06/12/leetcode-invert-binary-tree/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。