携手创作,一起成长!这是我参加「日新计划 8 月更文挑战」的第18天,点击检查活动详情
标题
给你一棵二叉树的根节点 root
,翻转这棵二叉树,并返回其根节点。
说明: xxx
示例 1:
- 输入:
root = [4,2,7,1,3,6,9]
- 输出:
[4,7,2,9,6,3,1]
示例 2:
- 输入:
root = [2,1,3]
- 输出:
[2,3,1]
示例 3:
- 输入:
root = []
- 输出:
[]
办法一:递归
思路及解法
这是一道很经典的二叉树问题。显然,咱们从根节点开端,递归地对树进行遍历,并从叶子节点先开端翻转。如果当时遍历到的节点 rootroot 的左右两棵子树都已经翻转,那么咱们只需求交流两棵子树的位置,即可完成以 rootroot 为根节点的整棵子树的翻转。
代码
class Solution {
func invertTree(_ root: TreeNode?) -> TreeNode? {
if nil == root {
return root
}
let left: TreeNode? = invertTree(root?.left)
let right: TreeNode? = invertTree(root?.right)
root?.left = right
root?.right = left
return root
}
}
复杂度剖析
-
时刻复杂度:O(N)O(N),其中 NN 为二叉树节点的数目。咱们会遍历二叉树中的每一个节点,对每个节点而言,咱们在常数时刻内交流其两棵子树。
-
空间复杂度:O(N)O(N)。使用的空间由递归栈的深度决议,它等于当时节点在二叉树中的高度。在平均情况下,二叉树的高度与节点个数为对数联系,即 O(logN)O(logN)。而在最坏情况下,树构成链状,空间复杂度为 O(N)O(N)。
办法二:迭代
思路及解法
递归实现也便是深度优先遍历的方法,那么对应的便是广度优先遍历。
广度优先遍历需求额定的数据结构–行列,来存放暂时遍历到的元素。
深度优先遍历的特点是一竿子插究竟,不行了再退回来继续;而广度优先遍历的特点是层层扫荡。
所以,咱们需求先将根节点放入到行列中,然后不断的迭代行列中的元素。
对当时元素互换其左右子树的位置,然后:
- 判别其左子树是否为空,不为空就放入行列中
- 判别其右子树是否为空,不为空就放入行列中
代码
class Solution {
func invertTree(_ root: TreeNode?) -> TreeNode? {
if nil == root {
return root
}
var queue: [TreeNode?] = []
queue.append(root)
while !queue.isEmpty {
let tmp: TreeNode? = queue.removeLast()
let left: TreeNode? = tmp?.left
tmp?.left = tmp?.right
tmp?.right = left
if tmp?.left != nil {
queue.append(tmp?.left)
}
if tmp?.right != nil {
queue.append(tmp?.right)
}
}
return root
}
}
复杂度剖析
-
时刻复杂度:每个节点都需求入行列/出行列一次,所以是 O(n)O(n)
-
空间复杂度:最坏的情况下会包含所有的叶子节点,彻底二叉树叶子节点是 n/2n/2 个,所以时刻复杂度是 O(n)O(n)