【力扣】94. 二叉树的中序遍历、144. 二叉树的前序遍历、145. 二叉树的后序遍历

  • 先序遍历:根-左-右
  • 中序遍历:左-根-右
  • 后序遍历:左-右-根

94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:
在这里插入图片描述

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

示例 2:

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

示例 3:

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

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解题方法

  • C 递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void inorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, resSize);  // 左子树
    res[(*resSize)++] = root->val;      // 根节点
    inorder(root->right, res, resSize); // 右子树
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

144. 二叉树的前序遍历

题目描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:
在这里插入图片描述

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

示例 2:

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

示例 3:

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

示例 4:

输入:root = [1,2]
输出:[1,2]

示例 5:

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

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

解题方法

  • C 递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void preorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    res[(*resSize)++] = root->val;       // 根节点
    preorder(root->left, res, resSize);  // 左子树
    preorder(root->right, res, resSize); // 右子树
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
}

145. 二叉树的后序遍历

题目描述

给你一棵二叉树的根节点 root ,返回其节点值的 后序 遍历 。

示例 1:
在这里插入图片描述

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

示例 2:

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

示例 3:

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

提示:

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

解题方法

  • C 递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void postorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    postorder(root->left, res, resSize);  // 左子树
    postorder(root->right, res, resSize); // 右子树
    res[(*resSize)++] = root->val;        // 根节点
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521030.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【ControlNet v3版本论文阅读】

网络部分最好有LDM或者Stable Diffusion的基础&#xff0c;有基础的话会看的很轻松 Abstract 1.提出了一种网络结构支持额外输入条件控制大型预训练的扩散模型。利用预训练模型学习一组不同的条件控制。 2.ControlNet对于小型&#xff08;<50k&#xff09;或大型&#xff…

vue项目使用element ui

目录 1、创建一个vue项目 2、找到element官网&#xff0c;点击指南&#xff0c;找到安装栏 3、 找到使用包管理器&#xff0c;复制命令 4、在main.js中引入element 5、使用element ui 6、找到App.vue&#xff0c;导入Button.vue文件&#xff0c;保存启动项目 1、创建一个vu…

千字深度理解:什么是电容的直流偏压特性?

原文来自微信公众号&#xff1a;工程师看海&#xff0c;与我联系&#xff1a;chunhou0820 看海原创视频教程&#xff1a;《运放秘籍》 大家好&#xff0c;我是工程师看海&#xff0c;很久没发千字长文了&#xff0c;原创文章欢迎点赞分享&#xff01; 电容是电路中最常用的被动…

GIt 删除某个特定commit

目的 多次commit&#xff0c;想删掉中间的一个/一些commit 操作方法 一句话说明&#xff1a;利用rebase命令的d表示移除commit的功能&#xff0c;来移除特定的commit # 压缩这3次commit,head~3表示从最近1次commit开始&#xff0c;前3个commit git rebase -i head~3rebase…

nest路由通配符使用

写法 路由路径 ‘ab*cd’ 将匹配 abcd 、ab_cd 、abecd 等。 src/cats/cats.controller.ts import { Controller, Get } from nestjs/common;Controller(cats) export class CatsController {Get(ab*cd)findAll1(): string {return 测试路由通配符;} }效果展示 截图1 截图2 …

蓝桥杯python组真题练习2

目录 1.裁纸刀 2.路径 3.排列字母 4.直线 5.纸张尺寸 1.裁纸刀 11.裁纸刀 - 蓝桥云课 (lanqiao.cn) import os import sys# 请在此输入您的代码sum 4 sum 19 sum 21*20 print(sum) 2.路径 12.路径 - 蓝桥云课 (lanqiao.cn) 这道题涉及到求两个数的最小公倍数。一开始…

企业如何设计和实施有效的网络安全演练?

现实世界中&#xff0c;武装部队一直利用兵棋推演进行实战化训练&#xff0c;为潜在的军事冲突做准备。随着当今的数字化转型&#xff0c;同样的概念正在以网络安全演习的形式在组织中得到应用&#xff0c;很多企业每年都会基于合理的网络攻击场景和事件响应做一些测试和模拟。…

Day:004(1) | Python爬虫:高效数据抓取的编程技术(数据解析)

数据解析-正则表达式 在前面我们已经搞定了怎样获取页面的内容&#xff0c;不过还差一步&#xff0c;这么多杂乱的代码夹杂文字我们怎样 把它提取出来整理呢&#xff1f;下面就开始介绍一个十分强大的工具&#xff0c;正则表达式&#xff01; 正则表达式是对字符串操作的一种…

【Python毕业设计】python基于CatBoost模型的混凝土强度预测研究(源码+数据集+毕业论文)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…

PAC与BTI、MTE的关系

PAC与BTI、MTE的关系如何&#xff1f;标记是否有冲突&#xff1f;

manga-ocr漫画日文ocr

github 下载 解压 anaconda新建环境 conda create -n manga_ocr python3.8 激活环境 conda activate manga_ocr cd到解压目录 cd /d manga-ocr-master 安装依赖包 pip install -r requirements.txt pip3 install manga-ocr 下载离线model huggingface 123云盘 解压到一个目录…

蓝桥真题--路径之谜DFS解法

路径之谜 思路 前置知识&#xff1a;深度搜索模板搜索所有可以找的路径&#xff0c;将走过的靶子减去一走到最后一个格子的时候&#xff0c;直接去判断所有的靶子只有除最后一个位置的靶子&#xff0c;其余靶子都归零的时候&#xff0c;判断一个最后一个位置横坐标和纵坐标的靶…

Stale Diffusion、Drag Your Noise、PhysReaction、CityGaussian

本文首发于公众号&#xff1a;机器感知 Stale Diffusion、Drag Your Noise、PhysReaction、CityGaussian Drag Your Noise: Interactive Point-based Editing via Diffusion Semantic Propagation Point-based interactive editing serves as an essential tool to compleme…

爬虫 新闻网站 以湖南法治报为例(含详细注释) V1.0

目标网站&#xff1a;湖南法治报 爬取目的&#xff1a;为了获取某一地区更全面的在湖南法治报已发布的宣传新闻稿&#xff0c;同时也让自己的工作更便捷 环境&#xff1a;Pycharm2021&#xff0c;Python3.10&#xff0c; 安装的包&#xff1a;requests&#xff0c;csv&#xff…

RabbitMQ3.13.x之七_RabbitMQ消息队列模型

RabbitMQ3.13.x之七_RabbitMQ消息队列模型 文章目录 RabbitMQ3.13.x之七_RabbitMQ消息队列模型1. RabbitMQ消息队列模型1. 简单队列2. Work Queues(工作队列)3. Publish/Subscribe(发布/订阅)4. Routing(路由)5. Topics(主题)6. RPC(远程过程调用)7. Publisher Confirms(发布者…

2024-04-26 学习笔记(工业大模型,SAM优化)

坚持每周一篇&#xff0c;加油。 1.穷人的思想钢印&#xff1a;踏实做事情&#xff0c;不做马屁精 摘要&#xff1a;大模型摘要和文章意思相反。。可知这个思想钢印也传递给了AI Raiden说&#xff1a;最近一直在想一句话&#xff1a;假如你混了很久还是一事无成&#xff0c;不…

JavaWeb前端基础(HTML CSS JavaScript)

本文用于检验学习效果&#xff0c;忘记知识就去文末的链接复习 1. HTML 1.1 HTML基础 结构 头<head>身体<body> 内容 图片<img>段落<p>图标<link> 标签 单标签双标签 常用标签 div&#xff1a;分割块span&#xff1a;只占需要的大小p&…

「 典型安全漏洞系列 」12.OAuth 2.0身份验证漏洞

在浏览网页时&#xff0c;你肯定会遇到允许你使用社交媒体帐户登录的网站。此功能一般是使用流行的OAuth 2.0框架构建的。本文主要介绍如何识别和利用OAuth 2.0身份验证机制中发现的一些关键漏洞。 1. OAuth产生背景 为了更好的理解OAuth&#xff0c;我们假设有如下场景&#…

全国日照时数空间分布数据/月度降雨量分布/月均气温分布

引言 地理遥感生态网结合1971-2021年各地区地面气象监测站数据&#xff0c;应用气候数据空间插值软件Anusplin预测全国日照时数分布数据成果。得出全国各个省市自治区日照时数分布图&#xff0c;全国各省市自治区日照时数数据产品是地理遥感生态网推出的气象气候类数据产品之一…

自定义实现shell/bash

文章目录 函数和进程之间的相似性shell打印提示符&#xff0c;以及获取用户输入分割用户的输入判断是否是内建命令执行相关的命令 全部代码 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#…