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

【面试HOT200】二叉树——深度优先搜索篇

系列综述:
💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于【CodeTopHot200】进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证,所有代码均优先参考最佳性能。
🤭结语:如果有帮到你的地方,就点个赞关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇


文章目录

    • 基础知识
      • 二叉树DFS基本算法
        • 递归算法
        • 非递归算法
      • 相关题目
        • 236. 二叉树的最近公共祖先
        • 110. 判断平衡二叉树(后序遍历的示例)
        • 222. 求树中结点的数量
        • 226. 翻转二叉树
        • 101. 对称二叉树
        • 左叶子之和
        • 二叉树的所有路径(带缓存的前序遍历)
        • 符合总和的路径
    • 参考博客


😊点此到文末惊喜↩︎

基础知识

二叉树DFS基本算法

递归算法
  1. 注意
    • 左右子树不需要if (root->left/rihgt),因为递归出口已经判断了
    • 后序遍历有个好处:可以先收集和处理孩子,然后根节点再进行处理
    // 前序遍历
    void Traversal(TreeNode *root) {if (root == nullptr) return ;Doing(root->val);       // 中Traversal(root->left);  // 左Traversal(root->right); // 右
    }
    // 中序遍历
    void Traversal(TreeNode *root) {if (root == nullptr) return ;Traversal(root->left);  // 左Doing(root->val);       // 中Traversal(root->right); // 右
    }
    // 后序遍历
    void Traversal(TreeNode *root, vector<int> vec) {if (root == nullptr) return ;Traversal(root->left);  // 左Traversal(root->right); // 右vec.emplace_back(root->val);// 中
    }
    
非递归算法
  1. 注意点
    vector<int> preorderTraversal(TreeNode* root) {vector<int> res;		// 结果容器stack<TreeNode*> st;	// 深度栈if(root != nullptr) st.push(root);	// 根非空则入栈// 遍历源容器while (!st.empty()) {	// key:注意使用的全部结点都是node// 先记录TreeNode *node = st.top();st.pop();// 后操作if (node != nullptr) {// 压入允许为逆序,注意根节点要后压入nullptrif (node->right) st.push(node->right);	if (node->left) st.push(node->left);	st.push(node);st.push(nullptr);} else {// 先记录node = st.top();st.pop();// 后操作res.emplace_back(node->val);}}return res;
    }
    

相关题目

236. 二叉树的最近公共祖先
  1. 题目
    • 给定一个二叉树, 找到该树中两个指定节点p和q的最近公共祖先。
  2. 复杂度分析:
    • 时间复杂度 O(N): 其中 N为二叉树节点数;最差情况下,需要递归遍历树的所有节点。
    • 空间复杂度 O(N): 最差情况下,递归深度达到 N
  3. 思路
    • 递归出口:如果不是nullptr表示找到了
    • 后序遍历:优先遍历左右子树并进行记录
    • 结点处理
      • 如果左右子树都非空,一定表示该结点为公共祖先结点
      • 如果有一个为空,则向上传递非空的那个结点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 递归出口:返回标志,不为空说明是祖先结点if (root == p || root == q || root == nullptr) return root;// 后序遍历TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);// 中间结点的处理// 左右都非空表示,该节点为公共祖先结点 if (left != nullptr && right != nullptr)return root;// 有一个为空表示,if (left == nullptr) return right;if (right == nullptr) return left;return root;
}
110. 判断平衡二叉树(后序遍历的示例)
  1. 递归法
    • 给定一个二叉树,判断它是否是高度平衡的二叉树。
    • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
    // 初始化ans为true,最后看ans是否为false即可
    int depth(TreeNode* root, bool &ans) {if(!root) return 0;// 后序遍历int left=1+depth(root->left, ans);int right=1+depth(root->right, ans);if(abs(left-right) > 1) ans = false;// 对根结点的处理// 递归出口return max(left,right);	// 返回树的高度
    }
    // 尾递归优化:效率高
    bool isBalanced(TreeNode* root) {if (root == nulllptr)  return true;return 	abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
    
222. 求树中结点的数量
  1. 题目
    • 给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
  2. 算法
    int getNodesNum(TreeNode* cur) {if (cur == NULL) return 0;int leftNum = getNodesNum(cur->left);      // 左int rightNum = getNodesNum(cur->right);    // 右int treeNum = leftNum + rightNum + 1;      // 中return treeNum;
    }
    
226. 翻转二叉树
  1. 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
    在这里插入图片描述
TreeNode* invertTree(TreeNode* root) {auto self = [&](auto &&self, TreeNode *root){if (root == nullptr) return ;self(self, root->left);self(self, root->right);swap(root->left, root->right);return ;};self(self, root);return root;
}
101. 对称二叉树
  1. 题目
    • 求一颗二叉树是否镜像对称
      在这里插入图片描述
  2. 思路
    • 根节点必定对称,关键是左右两子树的对称
    • 左右两个孩子存在的情况下,递归比较左右两颗子树的情况
bool isSymmetric(TreeNode* root) {auto self = [&](auto && self, TreeNode *left, TreeNode *right)->bool{// 递归出口if (left == nullptr && right == nullptr) return true;else if (left != nullptr && right == nullptr) return false;else if (left == nullptr && right != nullptr) return false;else if (left->val != right->val) return false;// 后序遍历:递归比较并汇总结果bool outside = self(self, left->left, right->right);bool inside = self(self,left->right, right->left);bool is_same = outside && inside;// 返回结果return is_same;};return self(self, root->left, root->right);
}
左叶子之和
  1. 求二叉树的左叶子之和
    • 遍历所有节点,对所求的特殊节点进行约束求值
    if (node->left != nullptr 
    && node->left->left == nullptr 
    && node->left->right == nullptr)res += node->left->val;
    
二叉树的所有路径(带缓存的前序遍历)
  1. 递归
    • 数字转化成字符串to_string(number)
    • 字符串后追加子串str.append(subStr)
    • 字符串删除某个位置之后的字符str.erase(position)
    // 数字型
    void dfs(TreeNode*root,vector<int>path, vector<vector<int>> &res) {if(!root) return;  //根节点为空直接返回// 中path.push_back(root->val);  //作出选择if(!root->left && !root->right) //如果到叶节点  {res.push_back(path);return;}// 左dfs(root->left,path,res);  //继续递归// 右dfs(root->right,path,res);
    }
    // 字符型
    void binaryTree(TreeNode* root,string path,vector<string>&res) {if(root==NULL) return ;path.append(to_string(root->val));path.append("->");if(root->left==NULL&&root->right==NULL{path.erase(path.length()-2);res.push_back(path);}binaryTree(root->left,path,res);binaryTree(root->right,path,res);
    }
    vector<string> binaryTreePaths(TreeNode* root) {string path;vector<string>res;binaryTree(root,path,res);return res;
    }
    
符合总和的路径
  1. 题目
    • 判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true;否则,返回 false
    // 递归方式:前序遍历,并记录每条路径的和
    bool hasPathSum(TreeNode* root, int targetSum) {bool flag = false;auto self = [&](auto &&self, TreeNode *root, int sum){// sum不可全局if (root == nullptr) return ;// 根结点的处理sum += root->val;cout << sum << ' ';if (root->left == nullptr && root->right == nullptr && targetSum == sum) flag = true;self(self, root->left, sum);self(self, root->right, sum);};self(self, root, 0);return flag;
    }
    // 非递归
    bool hasPathSum(TreeNode* root, int targetSum) {// 初始化stack<TreeNode*> st;if(root != nullptr) st.push(root);int sum = 0;// 迭代while(!st.empty()){TreeNode *cur = st.top();if(cur != nullptr){st.pop();st.push(cur);st.push(nullptr);sum += cur->val;if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);}else{st.pop();cur = st.top();st.pop();// 节点判断if(sum == targetSum&& cur->left == nullptr && cur->right == nullptr){return true;}else{// 回溯sum -= cur->val;}}}return false;
    }
    


少年,我观你骨骼清奇,颖悟绝伦,必成人中龙凤。
不如点赞·收藏·关注一波

🚩点此跳转到首行↩︎

参考博客

  1. 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解
  2. codetop
  3. 力扣(LeetCode)Krahets

相关文章:

【面试HOT200】二叉树——深度优先搜索篇

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于【CodeTopHot200】进行的&#xff0c;每个知识点的修正和深入主要参…...

价值投资选股的方法

价值投资法是一种长期投资策略&#xff0c;其核心思想是寻找被市场低估的股票&#xff0c;即股票的市场价格低于其内在价值。这种策略认为&#xff0c;投资者应该关注公司的基本面&#xff0c;如盈利能力、成长潜力、财务状况等&#xff0c;而不是短期的市场波动。以下是价值投…...

java中如何将mysql里面的数据取出来然后通过stream流的方式进行数据处理代码实例?

在 Java 中使用 Stream 流的方式从 MySQL 数据库中取出数据并进行处理&#xff0c;你可以通过 JDBC&#xff08;Java Database Connectivity&#xff09;来实现。下面是一个简单的代码示例&#xff1a; import java.sql.*; import java.util.stream.Stream; public class MySQ…...

C++服务器 支持http、tcp protobuf、websocket,linux开源框架 零依赖轻松编译部署 Reactor

开源地址: https://github.com/crust-hub/tubekit/tree/main Github:https://github.com/gaowanlu 诚招有兴趣的小伙伴加入开发维护 Tubekit The C TCP server framework based on the Reactor model continues to implement POSIX thread pool, Epoll, non blocking IO, obj…...

1688API接口系列,1688开放平台接口使用方案(商品详情数据+搜索商品列表+商家订单类)

1688商品详情接口是指1688平台提供的API接口&#xff0c;用于获取商品详情信息。通过该接口&#xff0c;您可以获取到商品的详细信息&#xff0c;包括商品标题、价格、库存、描述、图片等。 要使用1688商品详情接口&#xff0c;您需要先申请1688的API权限&#xff0c;并获取ac…...

CentOS服务器网页版Rstudio-server及R包批量安装最佳实践

CentOS服务器安装网页版Rstudio-server及R包批量安装 以下为CentOS 7/8的Rstudio-server安装、配置和R包安装操作 1. 软件包安装 Centos 7安装 # 下载安装包&#xff0c;大小115.14 MB wget -c https://download2.rstudio.org/server/centos7/x86_64/rstudio-server-rhel-…...

centos7内核升级(k8s基础篇)

1.查看系统内核版本信息 uname -r 2.升级内核 2.1更新yum源仓库 yum -y update更新完成后&#xff0c;启用 ELRepo 仓库并安装ELRepo仓库的yum源 ELRepo 仓库是基于社区的用于企业级 Linux 仓库&#xff0c;提供对 RedHat Enterprise (RHEL) 和 其他基于 RHEL的 Linux 发行…...

数据结构与算法设计分析——NP完全理论

目录 一、P类问题与NP类问题的定义二、常见的NP类问题&#xff08;一&#xff09;旅行商问题&#xff08;TSP&#xff09;&#xff08;二&#xff09;哈密尔顿回路问题&#xff08;三&#xff09;判断回路问题&#xff08;四&#xff09;图的着色问题&#xff08;五&#xff09…...

AGNES层次聚类

已知数据集D中有9个数据点&#xff0c;分别是(1,2)&#xff0c;(2&#xff0c;3)&#xff0c;(2,1), (3,1),(2,4),(3,5),(4,3),(1,5),(4,2)。要求&#xff1a; (1)采用层次聚类的聚集算法进行聚类&#xff0c;k2。 (2)距离计算采用欧几里得距离。 (3)簇之间的距离采用单链接方…...

HCIP —— 双点重发布 + 路由策略 实验

目录 实验拓扑&#xff1a; 实验要求&#xff1a; 实验配置&#xff1a; 1.配置IP地址 2.配置动态路由协议 —— RIP 、 OSPF R1 RIP R4 OSPF R2 配置RIP、OSPF 双向重发布 R3配置RIP、OSPF 双向重发布 3.查询路由表学习情况 4.使用路由策略控制选路 R2 R3 5.检…...

Python标准库:datetime模块【侯小啾python领航班系列(二十五)】

Python标准库:datetime模块【侯小啾python领航班系列(二十五)】 大家好,我是博主侯小啾, 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ…...

新版idea如何开启多台JVM虚拟机

1.看看自己的项目 2.可能开始的时候啥也没有&#xff0c;就点Run Configuration Type 3.再点击Edit Configurations... 4.点击号添加SpringBoot 5.主类选择一下&#xff0c;一般就一个&#xff0c;点他选了就行。 6.然后点击Modify Options 选择添加add VM Options 7.点击appl…...

软件工程单选多选补充

2. 4. 5. 6. 7. 8. 9. 10. 12。 13....

6-66.时间

本题要求输入小时、分钟和秒数&#xff0c;并将其输出。针对时间表示中出现的异常进行处理。例如小时数不应超过23&#xff0c;分钟不应超过59&#xff0c;秒数不应超过59。此外&#xff0c;以上三个变量均应大于等于0。 输入样例&#xff1a; 在这里给出三组输入。例如&…...

面试多线程八股文十问十答第一期

面试多线程八股文十问十答第一期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1.ThreadLocal如何实现线程安全 Java的ThreadLocal是一个线程本地变量&#xff0…...

Mybatis 操作续集(结合上文)

当我们增加一个数据之后,如果我们想要获取它的 Id 进行别的操作,我们该如何获取 Id 呢? 用那个Options package com.example.mybatisdemo.mapper;import com.example.mybatisdemo.model.UserInfo; import org.apache.ibatis.annotations.*;import java.util.List;Mapper pub…...

JVM基础篇:垃圾回收

目录 1.前言 1.1C/C的内存管理 1.2Java的内存管理 2.方法区的回收 3.堆回收 3.1引用计数法和可达性分析法 3.2五种对象引用 强引用 软引用 弱引用 虚引用 终结器引用 3.3垃圾回收算法评价标准 ①吞吐量 ②最大暂停时间 ③堆使用效率 3.4垃圾回收算法 ①标记清…...

蓝桥杯ACwing习题

题目 &#xff1a;https://www.acwing.com/problem/content/4409/ 解析 &#xff1a;根据题目我们可以知道 问的是方案数 那么首先就想到了 dp 仔细想一下 发现类似于蒙德里安的梦想那道状态压缩的题 &#xff0c; 所以我们先考虑怎么定义 f[i][j] f[i][j] 表示的是 已经放了…...

vue发送请求携带token,拼接url地址下载文件

封装请求 &#xff0c;该请求为普通的get请求 该请求返回值为&#xff1a; 请求成功之后拼接URL地址下载文件 代码块 downTemplateRequest(activeKeys.value).then((res) > {let url http://47.169.168.99:18888/media/${res.data.name};var elink document.createElemen…...

【PTA-C语言】编程练习3 - 循环结构Ⅱ

如果代码存在问题&#xff0c;麻烦大家指正 ~ ~有帮助麻烦点个赞 ~ ~ 编程练习3 - 循环结构&#xff08;9~15&#xff09; 7-9 特殊a串数列求和&#xff08;分数 15&#xff09;7-10 穷举法搬运砖块问题&#xff08;分数 15&#xff09;7-11 数字金字塔&#xff08;分数 15&…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...