六六力扣刷题二叉树之翻转二叉树

简介: 六六力扣刷题二叉树之翻转二叉树

前言

之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两天晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀

链表的合集

字符串

双指针

搜索二叉树

题目

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

 

示例 1:

image.png

输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 示例 2:

image.png

输入:root = [2,1,3] 输出:[2,3,1] 示例 3:

输入:root = [] 输出:[]

思路

我们在做二叉树题目时候,第一想到的应该是用 递归 来解决。 仔细看下题目的 输入 和 输出,输出的左右子树的位置跟输入正好是相反的,于是我们可以递归的交换左右子树来完成这道题。

其实就是交换一下左右节点,然后再递归的交换左节点,右节点 我们可以总结出递归的两个条件如下:

  • 终止条件:当前节点为 null 时返回
  • 交换当前节点的左右节点,再递归的交换当前节点的左节点,递归的交换当前节点的右节点

时间复杂度:每个元素都必须访问一次,所以是 O(n) 空间复杂度:最坏的情况下,需要存放 O(h) 个函数调用(h是树的高度),所以是 O(h)

class Solution {
  public TreeNode invertTree(TreeNode root) {
    //递归函数的终止条件,节点为空时返回
    if(root==null) {
      return null;
    }
    //下面三句是将当前节点的左右子树交换
    TreeNode tmp = root.right;
    root.right = root.left;
    root.left = tmp;
    //递归交换当前节点的 左子树
    invertTree(root.left);
    //递归交换当前节点的 右子树
    invertTree(root.right);
    //函数返回时就表示当前这个节点,以及它的左右子树
    //都已经交换完了
    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;
  }
}

结束

所有二叉搜索树是这样的,要不就是迭代,要么就是遍历,大家可以多练习看看,我是小六六,三天打鱼,两天晒网!

相关文章
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
43 1
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
26 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
20 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
18 2
|
2月前
【LeetCode】整数翻转
【LeetCode】整数翻转
20 1
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
21 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
23 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
22 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0