代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树

简介: 代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树

1. LeetCode 102. 二叉树的层序遍历

1.1 思路

  1. 二叉树的层序遍历就相当于图论里的广度优先搜索,之前的递归遍历就相当于图论里的深度优先搜索
  2. 只依赖二叉树的结构本身是无法做到层序遍历的,因此需要借助一个队列的数据结构
  3. 首先将根节点放入,每一层要记录当时队列的长度,这个长度就相当于这层有几个元素,然后根据这个长度把每一层的元素弹出放入一个集合中,因为层序遍历返回的是List<List<Integer>>,就相当于一个二维数组,每一层就是每一维,如果没有这个长度记录那么队列既有这一层又有下一层时就混乱了
  4. 在弹出元素时再判断这个元素是否有左右孩子,有就放入队列,在原本层里的元素都弹出后再记录新的长度,每弹出一个元素长度就--

1.2 代码

class Solution {
    public List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        func(root);
        return list;
    }
    public void func(TreeNode node){
        if(node==null)return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(node);
        int len=queue.size();
        List<Integer> tempList;
        TreeNode tempNode;
        while(!queue.isEmpty()){
            tempList=new ArrayList<>();
            len=queue.size();
            while(len-->0){
                tempNode=queue.poll();
                tempList.add(tempNode.val);
                if(tempNode.left!=null)queue.offer(tempNode.left);
                if(tempNode.right!=null)queue.offer(tempNode.right);
            }
            list.add(tempList);
        }
    }
}

2. LeetCode 226. 翻转二叉树

2.1 思路

  1. 应该用什么遍历方式?递归还是非递归?递归的话是前中后序?要把这些想清楚
  2. 前序和后序是最方便的,中序也可以但很麻烦
  3. 确定递归的参数和返回值:返回值TreeNode,参数TreeNode 根节点
  4. 终止条件:遇到空节点了,if(root==null)return root;
  5. 处理逻辑:以前序遍历为例,前序遍历是“根左右”,那么交换就是swap(root.left,root.right),然后递归调用函数,分别是invertTree(root.left),invertTree(root.right)
  6. 如果是后序遍历,那么就把swap写在左右子树的下面即可
  7. 为什么中序不可以呢?其实如果是把swap写在中间的话,那么先把左子树翻转了,再把左右子树swap,那么此时的左子树就是原来的右子树,但接下来是invertTree(root.right),就相当于又处理原来的左子树了,即原来的右子树就没有处理,所以我们把invertTree(root.right)改为invertTree(root.left)即可

2.2 代码

class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

3. LeetCode 101. 对称二叉树

3.1 思路

  1. 二叉树类的题目确定遍历顺序是很重要的,这题我们用递归的方式,应该用前中后哪个呢?这题只能用后序,后序是“左右根”,因为我们要不断收集左右孩子的信息返回给上一个(即父节点)节点,再收集左右孩子的信息返回给上一个节点,这样才能知道以这个左节点为根节点的树和右节点为根节点的树是否是可以相互翻转的。因为只有后续遍历,才能知道把底部的孩子的信息是否相等的信息返回给上一层
  2. 确认递归的参数和返回值:由于上述所说,是否是对称二叉树就是判断左右子树是否是可以翻转的,因此定义一个函数,传入左子树和右子树,返回值就是是否是可以翻转的
  3. 终止条件:如果左节点为空右节点不为空,就是不可翻转的就return false;如果左节点不为空右节点为空,同理return false;如果左右都为空就是可翻转的return true;如果左右都不为空但值不相等,就return false;如果左右节点不为空且值相等就继续向下遍历
  4. 处理单层递归的逻辑:因为我们要比较外侧节点和内侧节点,如果相同就为true。于是递归调用函数boolean outside= compare(left.left , right.right),这就是左孩子的左孩子和右孩子的右孩子,即外侧节点的比较;然后再比较内侧节点,boolean inside=compare(left.right , right.left),这就是左孩子的右孩子和右孩子的左孩子,即内侧节点
  5. 最后是用布尔值result=outside&&inside,同时外侧和内侧相同,这才说明是对称的,最后return result

3.2 代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        if(left==null&&right!=null)return false;
        else if(left!=null&&right==null)return false;
        else if(left==null&&right==null)return true;
        else if(left.val!=right.val)return false;
        boolean outside=compare(left.left,right.right);
        boolean inside=compare(left.right,right.left);
        boolean result=outside&&inside;
        return result;
    }
}
目录
打赏
0
0
0
0
9
分享
相关文章
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
53 2
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
66 5
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
102 5
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
113 0
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口

热门文章

最新文章