算法训练day18Leetcode找树左下角的值112路径总和106从中序和后续遍历构造二叉树

2024-01-21 12:04
文章标签 算法 二叉树 遍历 训练 路径 构造 从中 106 总和 后续 112 左下角 找树 day18leetcode

本文主要是介绍算法训练day18Leetcode找树左下角的值112路径总和106从中序和后续遍历构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

513 找树左下角的值

题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。示例 1:输入: root = [2,1,3]
输出: 1
示例 2:输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7提示:二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1

我的想法

找出深度最大的叶子节点，左遍历在前

题目分析

我们来分析一下题目：在树的最后一行找到最左边的值。

首先要是最后一行，然后是最左边的值。

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。

如果对二叉树深度和高度还有点疑惑的话，请看：110.平衡二叉树 (opens new window)。

所以要找深度最大的叶子节点。

那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

递归三部曲：

  1. 确定递归函数的参数和返回值
    参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。

本题还需要类里的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。

代码如下：

int maxDepth = INT_MIN;   // 全局变量 记录最大深度
int result;       // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int depth)
  1. 确定终止条件
    当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

代码如下：

if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;           // 更新最大深度result = root->val;   // 最大深度最左面的数值}return;
}
  1. 确定单层递归的逻辑
    在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：
                    // 中
if (root->left) {   // 左depth++; // 深度加一traversal(root->left, depth);depth--; // 回溯，深度减一
}
if (root->right) { // 右depth++; // 深度加一traversal(root->right, depth);depth--; // 回溯，深度减一
}
return;

acm模式完整代码

#include <iostream>
#include <memory>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root->left == nullptr && root->right == nullptr) {if(depth > maxDepth) {maxDepth = depth;result = root->val;}return;}if (root->left) {depth ++;traversal(root->left, depth);depth --;}if (root->right) {depth ++;traversal(root->right, depth);depth --;}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};int main() {// 使用智能指针创建树节点std::unique_ptr<TreeNode> node1 = std::make_unique<TreeNode>(1);std::unique_ptr<TreeNode> node2 = std::make_unique<TreeNode>(2);std::unique_ptr<TreeNode> node3 = std::make_unique<TreeNode>(3);std::unique_ptr<TreeNode> node4 = std::make_unique<TreeNode>(4);std::unique_ptr<TreeNode> node5 = std::make_unique<TreeNode>(5);std::unique_ptr<TreeNode> node6 = std::make_unique<TreeNode>(6);std::unique_ptr<TreeNode> node7 = std::make_unique<TreeNode>(7);// 组织成树（注意：这里我们使用裸指针，因为树的结构需要共享指针）node1->left = node2.get();node1->right = node3.get();node2->left = node4.get();node3->left = node5.get();node3->right = node6.get();node5->right = node7.get();// 使用 Solution 类的实例Solution solution;int result = solution.findBottomLeftValue(node1.get()); // 传递裸指针// 输出结果std::cout << "The bottom left value is: " << result << std::endl;// 智能指针自动释放内存return 0;
}

112 路径总和

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。叶子节点 是指没有子节点的节点。示例 1：输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

我的思路

遍历到叶子节点，记录过程中值相加

题目分析

递归
可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树

  1. 确定递归函数的参数和返回类型
    参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。

再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）

如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）

如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？

遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示

bool traversal(treenode* cur, int count)   // 注意函数的返回类型

2.确定终止条件
首先计数器如何统计这一条路径的和呢？

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。

如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。

如果遍历到了叶子节点，count不为0，就是没找到。

递归终止条件代码如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
  1. 确定单层递归的逻辑
    因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

if (cur->left) { // 左 （空节点不遍历）// 遇到叶子节点返回true，则直接返回trueif (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑
}
if (cur->right) { // 右 （空节点不遍历）// 遇到叶子节点返回true，则直接返回trueif (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑
}
return false;

以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。

回溯隐藏在traversal(cur->left, count - cur->left->val)这里， 因为把count - cur->left->val 直接作为参数传进去，函数结束，count的数值没有改变。

为了把回溯的过程体现出来，可以改为如下代码：

if (cur->left) { // 左count -= cur->left->val; // 递归，处理节点;if (traversal(cur->left, count)) return true;count += cur->left->val; // 回溯，撤销处理结果
}
if (cur->right) { // 右count -= cur->right->val;if (traversal(cur->right, count)) return true;count += cur->right->val;
}
return false;

完整代码

#include <iostream>
# include <memory>
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
private:bool traversal(TreeNode* cur, int count) {if (!cur->left && !cur->right && count == 0) return true;if (!cur->left && !cur->right) return false;if (cur->left) {count -= cur->left->val;if(traversal(cur->left, count)) return true;count += cur->left->val;}if (cur->right) {count -= cur->right->val;if (traversal(cur->right, count)) return true;count += cur->right->val;}return false;}
public:bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;return traversal(root, targetSum - root->val);}
};int main() {// 创建树节点std::unique_ptr<TreeNode> root = std::make_unique<TreeNode>(5);root->left = new TreeNode(4);root->left->left = new TreeNode(11);root->left->left->left = new TreeNode(7);root->left->left->right = new TreeNode(2);root->right = new TreeNode(8);root->right->left = new TreeNode(13);root->right->right = new TreeNode(4);root->right->right->right = new TreeNode(1);// 检查路径和Solution solution;bool hasPath = solution.hasPathSum(root.get(), 22);// 输出结果if (hasPath) {std::cout << "There is a path with sum 22." << std::endl;} else {std::cout << "There is no path with sum 22." << std::endl;}// 清理分配的内存delete root->left->left->left;delete root->left->left->right;delete root->left->left;delete root->left;delete root->right->right->right;delete root->right->right;delete root->right->left;delete root->right;return 0;
}

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

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例 1:输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:输入：inorder = [-1], postorder = [-1]
输出：[-1]提示:1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

我的想法

先后序遍历找到根节点，再用根节点再中序遍历中进行切割分为左序列和右序列

题目分析

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

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;}// 第四步：切割中序数组，得到 中序左数组和中序右数组// 第五步：切割后序数组，得到 后序左数组和后序右数组// 第六步root->left = traversal(中序左数组, 后序左数组);root->right = traversal(中序右数组, 后序右数组);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());

acm模式代码

#include <iostream>
#include <vector>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}};class Solution {
private:TreeNode* traversal(std::vector<int>& inorder, std::vector<int>& postorder) {if (postorder.size() == 0) return nullptr;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;}std::vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);std::vector<int> rightInorder(inorder.begin() + delimiterIndex +1, inorder.end());postorder.resize(postorder.size() - 1);std::vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());std::vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(std::vector<int> &inorder, std::vector<int> &postorder) {if (inorder.size() == 0 || postorder.size() == 0) return nullptr;return traversal(inorder, postorder);}
};void printTree(TreeNode* node) {if (node != nullptr) {printTree(node->left);printTree(node->right);std::cout << node->val << " ";}
}
int main() {// 创建中序和后序遍历的序列std::vector<int> inorder = {9, 3, 15, 20, 7};std::vector<int> postorder = {9, 15, 7, 20, 3};// 创建Solution实例并重建二叉树Solution solution;TreeNode* root = solution.buildTree(inorder, postorder);// 打印重建后的二叉树结构std::cout << "The reconstructed tree (inorder): ";printTree(root);std::cout << std::endl;// 注意：这里没有删除TreeNode的实例，实际应用中应考虑内存管理return 0;
}

今日学习的文章和视频链接

https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=8272bd48fee17396a4a1746c256ab0ae
https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF

这篇关于算法训练day18Leetcode找树左下角的值112路径总和106从中序和后续遍历构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/629479。

相关文章

Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
python安装完成后可以进行的后续步骤和注意事项小结

python安装完成后可以进行的后续步骤和注意事项小结

《python安装完成后可以进行的后续步骤和注意事项小结》本文详细介绍了安装Python3后的后续步骤,包括验证安装、配置环境、安装包、创建和运行脚本,以及使用虚拟环境,还强调了注意事项,如系统更新、... 目录验证安装配置环境（可选）安装python包创建和运行Python脚本虚拟环境（可选）注意事项安装
阅读更多...
python获取当前文件和目录路径的方法详解

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》：本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2