当前位置: 首页 > news >正文

笔试面试题——二叉树进阶(一)

在这里插入图片描述


📘北尘_:个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上,不忘来时的初心

文章目录

  • 一、根据二叉树创建字符串
    • 1、题目讲解
    • 2、思路讲解
    • 3、代码实现
  • 二、二叉树的分层遍历
    • 1、题目讲解
    • 2、思路讲解
    • 3、代码实现
  • 三、二叉树的最近公共祖先
    • 1、题目讲解
    • 2、思路讲解+递归展开图
    • 3、代码实现


一、根据二叉树创建字符串

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解

在这里插入图片描述
在这里插入图片描述

3、代码实现

class Solution {
public:string tree2str(TreeNode* root) {string s;if(root==nullptr)return s;s+=to_string(root->val);if(root->left  || (root->left==nullptr && root->right)){s+='(';s+=tree2str(root->left);s+=')';}if(root->right){s+='(';s+=tree2str(root->right);s+=')';}return s;}
};

二、二叉树的分层遍历

1、题目讲解

在这里插入图片描述

2、思路讲解

在这里插入图片描述

3、代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> s;vector<vector<int>>  vv;int levelsize;if(root){s.push(root);levelsize=1;}while(!s.empty()){vector<int> v;while(levelsize--){TreeNode* front=s.front();s.pop();v.push_back(front->val);if(front->left)s.push(front->left);if(front->right)s.push(front->right);    }vv.push_back(v);levelsize=s.size();}return vv;}
};

三、二叉树的最近公共祖先

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解+递归展开图

思路一:

在这里插入图片描述

思路二:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3、代码实现

代码一:

class Solution {
public:bool find(TreeNode* root,TreeNode* x){if(root==nullptr)return  false;if(root==x)return true;return (find(root->left,x)||find(root->right,x));}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p || root==q)return root;bool pleft=find(root->left,p);bool pright=!pleft;bool qleft=find(root->left,q);bool qright=!qleft;if((pleft && qright) || (pright && qleft)){return root;}if(pleft && qleft){return lowestCommonAncestor(root->left,p,q);}if(pright && qright){return lowestCommonAncestor(root->right,p,q);}return nullptr;}
};

代码二:

class Solution {
public:bool findpath(TreeNode* root,TreeNode* x,stack<TreeNode*>& st){if(root==nullptr)return false;st.push(root);if(root==x)return true;if(findpath(root->left,x,st))return true;if(findpath(root->right,x,st))return true;st.pop();return false;   }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath,qpath;findpath(root,p,ppath);findpath(root,q,qpath);while(ppath.size()!=qpath.size()){if(ppath.size()>qpath.size())ppath.pop();elseqpath.pop();}while(ppath.top()!=qpath.top()){ppath.pop();qpath.pop();}return  qpath.top();      }
};

相关文章:

笔试面试题——二叉树进阶(一)

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、根据二叉树创建字符串1、题目讲解2、思路讲解3、代码实现 二、二叉树的分层遍历1、题目讲…...

Java反射示例

Java反射示例 创建数据类型ReflectPoint.java package com.reflection;import java.util.Date;public class ReflectPoint {private Date birthday new Date();private int x;public int y;public String str1 "ball";public String str2 "basketball"…...

【WinForm.NET开发】实现使用后台操作的窗体

本文内容 创建使用后台操作的窗体使用设计器创建 BackgroundWorker添加异步事件处理程序添加进度报告和取消支持Checkpoint 如果某项操作需要很长的时间才能完成&#xff0c;并且不希望用户界面 (UI) 停止响应或阻塞&#xff0c;则可以使用 BackgroundWorker 类在另一个线程上…...

【操作系统和计网从入门到深入】(四)基础IO和文件系统

前言 这个专栏其实是博主在复习操作系统和计算机网络时候的笔记&#xff0c;所以如果是博主比较熟悉的知识点&#xff0c;博主可能就直接跳过了&#xff0c;但是所有重要的知识点&#xff0c;在这个专栏里面都会提到&#xff01;而且我也一定会保证这个专栏知识点的完整性&…...

四.Winform使用Webview2加载本地HTML页面并互相通信

Winform使用Webview2加载本地HTML页面并互相通信 往期目录本节目标核心代码实现HTML代码实现的窗体Demo2代码效果图 往期目录 往期相关文章目录 专栏目录 本节目标 实现刷新按钮点击 C# winform按钮可以调用C# winform代码显示到html上点击HTML按钮可以调用C# winform代码更…...

如何有效清理您的Python环境:清除Pip缓存

Python是一个广泛使用的高级编程语言&#xff0c;以其强大的库和框架而闻名。然而&#xff0c;随着时间的推移和不断安装新的包&#xff0c;Python环境可能会变得混乱不堪&#xff0c;尤其是pip缓存可能占用大量的磁盘空间。本文将向您展示如何有效地清理pip缓存&#xff0c;保…...

Jira 母公司全面停服 Server 产品,用户如何迁移至极狐GitLab

Jira 母公司即将全面停服旗下部分 Server 端产品的销售和服务支持&#xff01; Jira 母公司 Atlassian 在几年前确定了公司的战略为“全面上云”&#xff0c;为此做出了停止 Server 产品的销售和支持。整个时间线从 2021 年 2 月 2 日开始&#xff0c;直到今年 2 月 15 日&…...

Docker安装配置OnlyOffice

OnlyOffice 是一款强大的办公套件&#xff0c;你可以通过 Docker 轻松安装和部署它。本文将指导你完成安装过程。 步骤 1&#xff1a;拉取 OnlyOffice Docker 镜像 首先&#xff0c;使用以下命令从 Docker Hub 拉取 OnlyOffice Document Server 镜像&#xff1a; sudo docke…...

启动低轨道卫星LEO通讯产业与6G 3GPP NTN标准

通讯技术10年一个大跃进&#xff0c;从1990年的2G至2000年的3G网路&#xff0c;2010年的4G到近期2020年蓬勃发展的5G&#xff0c;当通讯技术迈入融合网路&#xff0c;当前的 5G 技术不仅可提供高频宽、低延迟&#xff0c;同时可针对企业与特殊需求以 5G 专网的模式提供各式服务…...

PICO Developer Center 创建和调试 ADB 命令

PICO 开发者中心概览 ADB 是一个轻量级的 Android 调试桥(Android Debug Bridge&#xff0c;简称 ADB)&#xff0c;用于与 Android 设备进行通信和调试。ADB提供了许多有用的功能&#xff0c;使开发人员能够轻松地管理和调试设备上的应用程序。 你可以使用 PDC 工具来调试系统…...

【VRTK】【PICO】如何快速创建一个用VRTK开发的PICO项目

【背景】 每次新建一个VRTK的PICO项目总是做一些重复工作,于是就想着搞成一个基本的包,把基本的设置都放进去,今后新做项目直接导这个包就行了。 完整资源包请见本篇博客的绑定资源。 【内容简介】 这个包是我为了快速开发基于VRTK的PICO应用设置的基础项目包。每次开发…...

国产操作系统:VirtualBox安装openKylin-1.0.1虚拟机并配置网络

国产操作系统&#xff1a;VirtualBox安装openKylin-1.0.1虚拟机并配置网络 openKylin 操作系统目前适配支持X86、ARM、RISC-V三个架构的个人电脑、平板电脑及教育开发板&#xff0c;可以满足绝大多数个人用户及开发者的使用需求。适用于在VirtualBox平台上安装openKylin-1.0.1…...

本地git切换地区后,无法使用ssh访问github 22端口解决方案

问题 由于放假回家&#xff0c;发现之前一直使用正常的git&#xff0c;与github无法通讯&#xff0c;pull和push都无法连接。报错如下&#xff1a; connect to host github.com port 22: Connection timed out fatal: Could not read from remote repository. 原因 可能是所…...

Chat2DB:AI赋能的多数据库客户端工具,开源领航未来数据库管理

Chat2DB&#xff1a;开源多数据库客户端的AI革新 Chat2DB使用教程:Chat2DB使用教程_哔哩哔哩_bilibili 引言&#xff1a; 随着企业数据的快速膨胀&#xff0c;数据库管理的复杂性也在增加。此时&#xff0c;一个能够跨越数据库边界、并且集成先进的AI功能的工具&#xff0c;不…...

SQL Server修改数据字段名的方法

1. ALTER TABLE语句修改 这是一种最常用的数据库更改字段的方法&#xff0c;使用Alter Table语句来更改数据库字段的名称。 一般格式如下&#xff1a; ALTER TABLE 表名 RENAME COLUMN 原字段名 TO 新字段名; 例如&#xff0c;修改字段名字段名从UserName到Uname&#xff1a;…...

Flutter编译报错Connection timed out: connect

背景&#xff1a;用Android Studo 创建了Flutter项目&#xff0c;编译运行报错java.net.ConnectException: Connection timed out: connect 我自己的环境&#xff1a; windows11 Android Studio Flutter 截图如下&#xff1a; 将错误日志展开之后&#xff1a; Exception…...

PG DBA培训26:PostgreSQL运维诊断与监控分析

本课程由风哥发布的基于PostgreSQL数据库的系列课程&#xff0c;本课程属于PostgreSQL Diagnosis and monitoring analysis&#xff0c;学完本课程可以掌握PostgreSQL日常运维检查-风哥PGSQL工具箱&#xff0c;风哥专用PGSQL工具箱介绍&#xff0c;风哥专用PGSQL工具箱使用&…...

运维之道—生产环境安装Redis

目录 1.前言 2.环境准备 2.1 安装gcc依赖 3.部署安装 3.1 下载redis安装包 3.2 解压并编译安装redis 3.3 配置redis ​编辑3.4 启动redis并测试 4. 总结 1.前言 大家好,运维之道的系列文章继续进行,我们今天整理的是Redis生产环境的安装,Redis的安装以及生产环境的…...

人工智能数学验证工具LEAN4【入门介绍3】乘法世界-证明乘法的所有运算律

视频链接&#xff0c;创作不易记得投币哦&#xff1a; import Game.Levels.Multiplication.L08add_mul World "Multiplication" Level 9 Title "mul_assoc" namespace MyNat Introduction " We now have enough to prove that multiplication is a…...

Armv8-M的TrustZone技术简介

TrustZone技术是适用于Armv8-M的可选安全扩展,旨在为各种嵌入式应用提供改进的系统安全基础。 TrustZone技术的概念并不新鲜。该技术已经在Arm Cortex-A系列处理器上使用了几年,现在已经扩展到Armv8-M处理器。 在high level上,TrustZone技术适用于Armv8-M的概念与Arm Cort…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...