Studying-代码随想录训练营day16| 513找到左下角的值、112.路径总和、106从中序与后序遍历序列构造二叉树

本文主要是介绍Studying-代码随想录训练营day16| 513找到左下角的值、112.路径总和、106从中序与后序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第十六天,二叉树part03💪💪💪,编程语言:C++

目录

513找到左下角的值

112.路径总和

113.路径总和II

106从中序与后序遍历序列构造二叉树 

105.从前序与中序遍历序列构造二叉树 

总结 


513找到左下角的值

文档讲解:代码随想录找到左下角的值

视频讲解:手撕找到左下角的值

题目:

学习:注意是找到最底层最左边的值,而不是找到最左边的左节点。两者是有很大差别的,对于第二个示例就能看出,并且最底层最左边的值也未必是左节点,如果示例2中4有一个右节点,那最底层最左边的值就是4的右节点了。

代码:因此本题采用层序遍历最好理解,每次从左到右遍历,记入每次遍历的第一个节点,就是该层最左边的节点,直到找到最后一层。

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if(root != nullptr) que.push(root);int result;while(!que.empty()) {int size = que.size();result = que.front()->val;while(size--) {TreeNode* node = que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right); }}return result;}
};

代码:本题还可以采用递归遍历的方式,使用前序,中序,后序都可以,这三种遍历方式都保证了先遍历左子树,再遍历右子树。注意每次更新result,只在进入到一个更大的深度,这样能保证记录的是最左边的值。

class Solution {
public://设置两个全局变量,保存最大深度和答案值,当然本题也可以将其放入函数当中,使用引用的方式int maxDepth = INT_MIN;int result;void traversal(TreeNode* cur, int depth) {if(cur->left == nullptr && cur->right == nullptr) {if (depth > maxDepth) {maxDepth = depth;result = cur->val;}}//注意必须得先遍历左边,左优先遍历,能够保证在找到最后一层的时候,赋值最左边的节点if(cur->left) traversal(cur->left, depth + 1);if(cur->right) traversal(cur->right, depth + 1);}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

112.路径总和

文档讲解:代码随想录路径总和

视频讲解:手撕路径总和

题目:

学习:

  1. 依据本题的意思,我们在遍历过程中,需要遍历到叶子节点才终止。注意本题不适合进行值的大小判断,因为本题的节点数值和目标值都是有可能是正,有可能是负的,因此不好设置大小判断条件。
  2. 本题可以采取前序遍历的方式,同时在遍历的过程中,不是累加各节点数值,而是通过对目标值的相减,来不断逼近目标值,这样更加的直观,且能减少不必要的变量。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:bool traversal(TreeNode* root, int count) {//减掉当前节点的值count -= root->val;//确定终止条件,遍历到叶子结点if(root->left == nullptr && root->right == nullptr && count != 0) return false;if(root->left == nullptr && root->right == nullptr && count == 0) return true;//确定单层递归逻辑,同时保证遍历过程中root不为nullptr//count非引用方式,因此为自动进行回溯if (root->left) {if(traversal(root->left, count)) return true;} if (root->right) {if(traversal(root->right, count)) return true;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;return traversal(root, targetSum);}
};

113.路径总和II

题目:

学习:

  1. 本题与上题不同的在于,要找到所有的数值之和等于目标值的路径。因此我们需要遍历所有的节点,同时要持续记录数值和路径两个变量。数值通过上题,我们知道可以通过目标值不断做减法来进行记录,路径则需要我们建立一个数组来进行保存。
  2. 本题还有一个值得注意的地方,我们在递归过程中如果需要不停改变一个变量,一般采用的是引用的方式。但其实也能采用全局变量的方式,将变量写在函数外,全局变量在递归中同样会不断的被改变。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public://构造两个全局变量,存储路径和结果,取代参数引用vector<vector<int>> result;vector<int> path;//遍历树的节点,因为结果都储存在两个vector数组中,因此不需要返回值void traversal (TreeNode* root, int sum) {//确定终止条件//找到叶子节点的时候进行判断if(root->left == nullptr && root->right == nullptr && sum == 0) {result.push_back(path);return;}//如果sum!=0 直接返回if(root->left == nullptr && root->right == nullptr) return;//确定单层递归逻辑if(root->left) {path.push_back(root->left->val);traversal(root->left, sum - root->left->val);//对路径进行回溯path.pop_back();}if(root->right) {path.push_back(root->right->val);traversal(root->right, sum - root->right->val);path.pop_back();}return;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == nullptr) return result;path.push_back(root->val);traversal(root, targetSum - root->val);return result;}
};

106从中序与后序遍历序列构造二叉树 

文档讲解:代码随想录从中序与后序遍历系列构造二叉树

视频讲解:手撕从中序与后序遍历序列构造二叉树

题目:

学习: 本题与KMP算法一样,都是数据结构中经典的例题之一。

  1. 依据后序遍历左右中的特点我们可以知道,最后一个节点一定是根节点。而根据中序遍历左中右的特点,当我们知道谁是根节点之后,在中序遍历中根节点左边的部分就为根节点的左子树,右边的部分就为根节点的右子树。
  2. 接着我们重复上述过程,当找到根节点的左子树和右子树有哪些节点后,我们在后序遍历中也能够把除最后一个节点(根节点)以外的点,分为左子树部分和右子树部分。相对的对于这两个部分而言,由于后序遍历左右中的特点,最后一个节点就为它们各自的根节点(整棵树的中间节点)。之后再从中序遍历中依次找到根节点的左右部分即可循环下去,直到确定所有节点的位置。
  3. 如果是在纸上进行作答的话,我们根据一次次循环就很容易能够把节点加上去。但是在代码中我们要十分注意递归循环的过程,不仅要设置递归三部曲,还要划分好每次循环过程中的左子树部分和右子树部分。

本题的代码过程可以分为六步:

  1. 如果数组大小为零,说明是空节点,返回
  2. 如果不为空,取后序遍历数组的最后一个元素作为根节点元素。
  3. 找到后序遍历数组最后一个元素在中序遍历数组的位置,作为左右子树切割点。
  4. 切割中序遍历数组,切成中序左数组和中序右数组。
  5. 切割后序遍历数组,注意这里分割的方法是通过第4部分割出的两个数组来进行分割的,因为中序遍历数组中,中序左数组的个数(左子树)一定和后序遍历数组中后序左数组(左子树)的个数是一样的,右子树同理。(其实我们在用纸笔解答的时候,也是通过中序遍历数组分割后的结果,来推导后序遍历数组中的左右子树部分)
  6. 递归处理左区间和右区间。

代码:

class Solution {
private:TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {if (postorder.size() == 0) return NULL;// 后序遍历数组最后一个元素,就是当前的中间节点int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 叶子节点if (postorder.size() == 1) return root;// 找到中序遍历的切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左闭右开区间:[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开,注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

代码:本题也可以通过设置下标来设置左右子树区间

 

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
private:// 中序区间:[inorderBegin, inorderEnd),后序区间[postorderBegin, postorderEnd)TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {if (postorderBegin == postorderEnd) return NULL;int rootValue = postorder[postorderEnd - 1];TreeNode* root = new TreeNode(rootValue);if (postorderEnd - postorderBegin == 1) return root;int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左中序区间,左闭右开[leftInorderBegin, leftInorderEnd)int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 右中序区间,左闭右开[rightInorderBegin, rightInorderEnd)int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;// 切割后序数组// 左后序区间,左闭右开[leftPostorderBegin, leftPostorderEnd)int leftPostorderBegin =  postorderBegin;int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size// 右后序区间,左闭右开[rightPostorderBegin, rightPostorderEnd)int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素,已经作为节点了root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;// 左闭右开的原则return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());}
};

105.从前序与中序遍历序列构造二叉树 

题目:

学习:本题和上一题一样,只不过后序换为前序遍历后,根节点的寻找变为了找前序遍历数组的第一个节点作为根节点,剩下的同样是依据需要划分不同左右子树区间,进行递归。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
private:TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {if (preorderBegin == preorderEnd) return NULL;int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0TreeNode* root = new TreeNode(rootValue);if (preorderEnd - preorderBegin == 1) return root;int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 中序左区间,左闭右开[leftInorderBegin, leftInorderEnd)int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 中序右区间,左闭右开[rightInorderBegin, rightInorderEnd)int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;// 切割前序数组// 前序左区间,左闭右开[leftPreorderBegin, leftPreorderEnd)int leftPreorderBegin =  preorderBegin + 1;int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);int rightPreorderEnd = preorderEnd;root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);return root;}public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (inorder.size() == 0 || preorder.size() == 0) return NULL;// 参数坚持左闭右开的原则return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());}
};

注:本题还能采用迭代的方式,等我二刷试试。

总结 

今天题目虽然不多,但是难度都很大,需要反复学习理解。

  1. 左下角的值要避免成为找最左边的左叶子节点的值。
  2. 路径总和要注意对路径中数值的处理,以及路径总和II中对每一条路径的保存和回溯,都需要注意。
  3. 从中序与后序遍历构造二叉树和从前序与中序遍历构造二叉树,理解上虽然没什么问题,但是代码书写上难度很大,还需要多加练习。

这篇关于Studying-代码随想录训练营day16| 513找到左下角的值、112.路径总和、106从中序与后序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1083255

相关文章

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论