102. 二叉树的层序遍历 ,226.翻转二叉树 ,101.对称二叉树 2

简介: 本文介绍了三道经典的二叉树问题及其解法:**层序遍历**、**翻转二叉树**和**对称二叉树**。 - **层序遍历**使用队列实现广度优先搜索(BFS),逐层从左到右访问节点。 - **翻转二叉树**通过递归交换左右子树,简单高效。 - **对称二叉树**借助递归比较左右子树是否镜像对称。 总结指出,解决二叉树问题需明确遍历顺序(前序、中序、后序或层序),避免稀里糊涂解题。掌握通用方法论,才能灵活应对各类问题。

题目:102. 二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

输入:root = [3,9,20,null,null,15,7]

输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]

输出:[[1]]

示例 3:

输入:root = []

输出:[]

提示:

树中节点数目在范围 [0, 2000] 内

-1000 <= Node.val <= 1000

思考过程与知识点:

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。

题解:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }
 
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
       
        return ret;
    }
};

 

题目:226. 翻转二叉树

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

示例 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 = []

输出:[]

提示:

树中节点数目范围在 [0, 100] 内

-100 <= Node.val <= 100

题解:

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

题目:101. 对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]

输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]

输出:false

提示:

树中节点数目在范围 [1, 1000] 内

-100 <= Node.val <= 100

题解:

class Solution {
public:
    bool 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;
 
        // 此时就是:左右节点都不为空,且数值相同的情况
        // 此时才做递归,做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树:左、 右子树:右
        bool inside = compare(left->right, right->left);    // 左子树:右、 右子树:左
        bool isSame = outside && inside;                    // 左子树:中、 右子树:中 (逻辑处理)
        return isSame;
 
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

总结:

针对二叉树的问题,解题之前一定要想清楚究竟是前中后序遍历,还是层序遍历。

二叉树解题的大忌就是自己稀里糊涂的过了(因为这道题相对简单),但是也不知道自己是怎么遍历的。

这也是造成了二叉树的题目“一看就会,一写就废”的原因。

针对翻转二叉树,我给出了一种递归,三种迭代(两种模拟深度优先遍历,一种层序遍历)的写法,都是之前我们讲过的写法,融汇贯通一下而已。

大家一定也有自己的解法,但一定要成方法论,这样才能通用,才能举一反三!


相关文章
|
10月前
|
IDE 编译器 开发工具
【2026最新】Dev C++下载安装使用全流程教程(附最新版安装包+图文步骤)
Dev C++ 是一款轻量免费的 Windows C/C++ 集成开发环境,内置 MinGW 编译器,支持 C++11 等标准。安装简便、启动快速,适合新手学习、竞赛与算法训练,是入门 C/C++ 的理想工具。
5181 9
|
4月前
|
人工智能 弹性计算 自然语言处理
让 AI Agent 更懂 Terraform:用 Alibaba Cloud Agent Toolkit 生成和纳管阿里云资源
面向希望使用 Terraform 管理阿里云基础设施的开发者和企业用户,Alibaba Cloud Agent Toolkit 新增 Terraform 能力,覆盖 IaC 落地的两个关键入口:新资源建设与存量资源纳管。通过自然语言生成 Terraform HCL、存量资源导入 Terraform、IaCService Schema 实时查询、ResourceCenter 资源发现以及 Terraform Validate / Plan 校验闭环,Toolkit 让 AI Agent 不再只依赖模型记忆,而是基于真实云资源上下文辅助用户生成、迁移和持续治理阿里云资源。
533 0
|
4月前
|
人工智能 自然语言处理 算法
用AI标书工具辅助编写技术标书半年:聊聊踩过的坑与选型思路
本文分享团队半年AI辅助标书实践:从踩坑废标到构建选型方法论。强调“先拆解再生成”,区分通用模型与垂直工具;按项目等级(普通/商业/央企)匹配工具;重视全流程闭环与私有知识库沉淀;提出合规、安全、专业、协同四大选型硬标准。
|
4月前
|
人工智能 前端开发 算法
别再只盯着Java八股文!大模型时代,测试岗面试题已经彻底变了
2026年测试面试已巨变:告别Java八股与LeetCode,转向AI工程能力实战。大厂聚焦Agent异常处理、Harness驾驭工程、大模型幻觉测试等真场景问题,考察候选人对AI系统的设计、落地与质量保障能力——不会建测试Agent,就难进一线团队。
|
5月前
|
人工智能 算法 数据挖掘
DeepSeek 公式怎么导出 Word?完整保留 LaTeX 数学公式的 3 种方法
DeepSeek生成的数学公式导出到Word常遇显示异常、不可编辑等问题。本文详解三种解决方案:手动LaTeX复制(适合少量公式)、Markdown/Pandoc转换(适合技术用户批量处理)、DS随心转插件(一键在AI页面导出可编辑Word),助你高效保留公式结构与准确性。(239字)
1097 1
|
7月前
|
弹性计算 应用服务中间件 网络安全
企业网站建设实战:PageAdmin定制开发 + 阿里云服务器部署
分享PageAdmin+阿里云ECS的企业建站实战经验,从选型到部署全流程解析,99元/年低成本方案,适合中小企业快速搭建高性价比官网。
486 4
|
人工智能 数据库 云计算
🔥躺着赚佣金!阿里云推荐计算巢服务让你轻松"带货"云计算
阿里云推出“推荐服务赚佣金”计划,无需技术背景,分享链接即可轻松赚取额外收入。高达20%佣金,200+精选服务任选,实时追踪收益,适合个人推广的数字副业!
1100 9
|
Ubuntu Linux
计算机基础知识:linux系统怎么安装?
在虚拟机软件中创建一个新的虚拟机,并选择相应操作系统类型和硬盘空间大小等参数。将下载的 ISO 镜像文件加载到虚拟机中。启动虚拟机,进入安装界面,并按照步骤进行安装。安装完成后,可以在虚拟机中使用 Linux 系统。
|
9月前
|
数据采集 人工智能 运维
工业场景下AR+AI图像识别:精准选型赋能运维与质检
本文解析AR+AI图像识别在工业质检与运维中的适配逻辑:明确5类不适配场景(空间受限、高速动态、细微特征、近距离读取、全自动产线)及5类高价值适配场景(传统产线、经验依赖、疲劳检测、高风险环节、多流程运维),助力企业科学选型,避免技术错配,夯实数字化转型基础。(239字)