二叉树——226. 翻转二叉树
1 题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
2 题目示例
在这里插入图片描述
在这里插入图片描述
示例 3：
输入：root = [] 输出：[]
3 题目提示
树中节点数目范围在 [0, 100] 内 -100 <= Node.val <= 100
4 思路
递归： 这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点root的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root为根节点的整棵子树的翻转。 复杂度分析 时间复杂度:o(N)，其中N为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。 ·空间复杂度:O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即O(log N)。而在最坏情况下，树形成链状，空间复杂度为O(N)。
迭代：
递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。 广度优先遍历需要额外的数据结构–队列，来存放临时遍历到的元素。 深度优先遍历的特点是一竿子插到底，不行了再退回来继续;而广度优先遍历的特点是层层扫荡。 所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。 对当前元素调换其左右子树的位置，然后: 判断其左子树是否为空，不为空就放入队列中判断其右子树是否为空，不为空就放入队列中 时间复杂度:同样每个节点都需要入队列/出队列—次，所以是o(n) 空间复杂度:最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是n/2个，所以时间复杂度是0(n)
5 我的答案
递归：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}迭代：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
