个人中心
文章发布
退出
作者热门文章
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
24
4
题目地址: https://leetcode.com/problems/invert-binary-tree/
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
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 f*** off.
翻转二叉树。
这个题能够很好地帮助我们理解递归。
递归函数本身也是函数，调用递归函数就把它当做普通函数来看待，一定要只思考当前层的处理逻辑，明白该递归函数的输入输出是什么即可，调用的时候不要管函数内部实现。不要用肉脑 debug 递归函数的调用过程，会被绕进去。
首先来分析invertTree(TreeNode root)函数的定义：
1、 函数的定义是什么？该函数可以翻转一棵二叉树，即将二叉树中的每个节点的左右孩子都进行互换；
2、 函数的输入是什么？函数的输入是要被翻转的二叉树；
3、 函数的输出是什么？返回的结果就是已经翻转后的二叉树；
然后我们来分析函数的写法：
1、 递归终止的条件当要翻转的节点是空，停止翻转，返回空节点；
2、 返回值虽然对root的左右子树都进行了翻转，但是翻转后的二叉树的根节点不变，故返回root节点；
3、 函数内容root节点的新的左子树：是翻转了的root.right=>即root.left=invert(root.right);root节点的新的右子树：是翻转了的root.left=>即root.right=invert(root.left);；
至此，递归函数就写完了。在『函数内容』编写的时候，是不是把递归函数invertTree(TreeNode root)当做了普通函数来用？调用invertTree(TreeNode root)函数就是能实现翻转二叉树的目的，不需要理解函数内部怎么实现的。
最后，提醒大家避免踩一个小坑，不能直接写成下面这样的代码：
root.left = invert(root.right)
root.right = invert(root.left)
1 2
这是因为第一行修改了root.left，会影响了第二行。在 Python 中，正确的写法是把两行写在同一行，就能保证 root.left 和 root.right 的修改是同时进行的。
Python 解法如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
使用迭代方法。众所周知，把递归改成迭代需要一个栈，这个题使用迭代基本就是套个模板就好了，关键步骤只有一行，那就是把两个子树进行翻转。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
stack = []
stack.append(root)
while stack:
node = stack.pop()
if not node:
continue
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
24
4
0
我正在阅读有关 Elasticsearch 的信息。看起来它维护所有文档中所有术语的倒排索引。但它是否也保持正常的索引，即从文档 id 到文档？此外，由于它在所有字段和所有术语上维护大量索引，所以它占
我正在做一个时间序列问题。当我在做 AR 模型时，一切正常。 # Import the module for estimating an ARMA model from statsmodels.tsa
是否可以使用Scala解析器组合器反转匹配？我正在尝试使用不以一组关键字开头的解析器来匹配行。我可以使用一个烦人的零宽度负前瞻正则表达式(例如"(?!h1|h2).*")来做到这一点，但我宁愿使用Sc
假设我有一个可以接受 optional 参数的函数，如果参数是 Some，我想返回 None，如果参数是 0x251812231343，则返回 None: def foo(a: Option[A]):
根据我对集合论的了解，当您取两个集合的并集时，您会覆盖两个集合并取结果集。当你取两个集合的交集时，你将两个集合重叠并取彼此重叠的部分。 对于数字，这很好用: type SomeUnion = (1 |
我有一个日期时间列表，我需要“反转”(因为缺少更好的词)这个列表。 public class Available { public Available(DateTime startDate,
我正在尝试反转键/值。 所以，我正在尝试这样的事情: var _ = require('underscore'); var myObj = [ {'name': 'Mike', 'number
是否有任何 .NET 类型可以表示一组键值对，其中每个键仅与单个值配对(如常规 Dictionary )，但每个值也仅与单个键配对？我一直认为这是一个“可逆”字典，因为您可以将键与值交换而不会发生任何
我正在寻找一种使用 NUnit 编写单元测试的方法，这样如果当前测试需要超过 X 毫秒才能完成，它应该终止并将其报告为已跳过/成功，但不会失败。这基本上与 NUnit Timeout 相反属性。 该问
下面的查询是我之前使用的...但是我想结合这两个查询以提高性能 select a, b, c from table1 where d LIKE 'xxx' and f like 'yyyy
当我运行这段代码时出现错误， at javaapplication1.JavaApplication1.bigger(JavaApplication1.java:32) (反向警告)，但是我已经
使用 SQL。我正在尝试列出所有城市的人口总数少于 10 万的每个国家/地区的名称。 下面的代码为我提供了拥有超过 100 000 人的城市的每个国家/地区，因此根据术语，我试图“反转”输出以列出此时
我正在创建一个 iOS 用户界面，允许用户在现有图像中选择一个矩形，将该矩形的角拖动到所需的大小。我现在有四个自定义 UIButton(30% alpha)和一个在四个角按钮之间绘制虚线的自定义 Vi
我需要更改现有的映射，将键交换为值，将值交换为键。由于我的映射中的键有重复值，因此我无法使用下划线库的 _.invert() 。 function map() { return {
我想以最好的 numpythonic 方式解决的问题是:我有一个二维索引列表 A，例如: A = [(0, 3), (2, 2), (3, 1)] 我的目标是现在得到一个数组 [[H H H 0],
我有一个二值图像，尺寸为 64x63，其中每个像素都是 1 或 0。 import struct from PIL import Image import numpy ... i1 = Image.f
假设我有一个整数数组 A 使得 A[i] = j，我想“反转它”；也就是说，创建另一个整数数组 B 使得 B[j] = i。 这对于任何语言的线性时间程序来说都是微不足道的；这是一个 Python 示
我是一个非常没有经验的 C 学习者，我在这段代码中收到了警告，它应该在调用时反转作为命令的第一个参数传递的字符串(在 Linux Ubuntu 中编程)。 警告是:14:9: warning: ass
MySQL (Innodb) 使用倒排索引还是正向索引？ 来自文章What's the difference between an inverted index and a plain old ind
本文主要是利用Python的第三方库Pillow，实现单通道灰度图像的颜色翻转功能。 ?
我是一名优秀的程序员,十分优秀！