[代码随想录Day16打卡] 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树

找树左下角的值

定义：二叉树中最后一行最靠左侧的值。
前序，中序，后序遍历都是先遍历左然后遍历右。
因为优先遍历左节点，所以递归中因为深度增加更新result的时候，更新的值是当前深度最左侧的值，到最后就得到了最后一行最靠左的节点。
注意：其中也有回溯，depth++; traversal(root->left,depth); depth–;这里，为什么用函数处理完之后depth要–？因为在处理完左节点的深度后，要减掉左节点的深度，然后再处理右节点的深度。
下面是C++, JAVA, Python的代码。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     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中的最小值int result;//记录节点的值void traversal(TreeNode* root, int depth){if(root->left == NULL && root->right == NULL){if(depth > maxDepth){maxDepth = depth;result = root->val;//如果深度增加就更新result保存的节点的值，因为遍历顺序是坐在右的前面所以能让result更新的一定是当前深度下的最左边的节点}}//然后处理左节点的值if(root->left){depth++;traversal(root->left, depth);depth--;//回溯}//这三行就相当于traversal(root->left, depth+1)//做了++操作但是没有改变depth的值if(root->right){depth++;traversal(root->right, depth);depth--;}}int findBottomLeftValue(TreeNode* root) {int depth = 0;traversal(root, depth);return result;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int maxDepth = -1;private int result;void traversal(TreeNode root, int depth){if(root.left == null && root.right==null){//碰到叶子节点了来比较当前叶子节点的深度和最大深度if(depth > maxDepth){maxDepth = depth;result = root.val;}}//处理左节点if(root.left!=null){depth++;traversal(root.left, depth);depth--;//这三行相当于traversal(root.left, depth+1)}//处理右节点if(root.right!=null){depth++;traversal(root.right, depth);depth--;//这三行相当于traversal(root.right, depth+1)}}public int findBottomLeftValue(TreeNode root) {int depth = 0;traversal(root, depth);return result;}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def traversal(self, root, depth):if root.left==None and root.right==None:if depth > self.maxDepth:#如果当前深度比最大深度大，更新result的值self.maxDepth = depthself.result = root.valif root.left!=None:depth+=1self.traversal(root.left, depth)depth-=1if root.right!=None:depth+=1self.traversal(root.right, depth)depth-=1def findBottomLeftValue(self, root):""":type root: Optional[TreeNode]:rtype: int"""self.maxDepth = -1self.result = Nonedepth = 0self.traversal(root, depth)return self.result

参考文章

  1. https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

路径总和

在这里插入图片描述

我们在递归外面用目标值减去根节点的值得到新的目标值，这样之后不必处理中也就是节点本身，而是处理节点的左右子节点。前中后序都一样（因为没有对中进行操作，只对左右进行操作）。

  1. 确定递归函数的参数和返回值：参数node和 count，输出是bool类型。如果它遍历的一条子路径符合要求就一层一层向上返回true。
  2. 确定终止条件：因为对左右子节点进行操作，所以要避免左右子节点为空，如果为空，count为0符合要求返回True，如果左右节点为空，count不为0不符合要求，返回False。
  3. 确定单层递归的逻辑：count减去当前的left/right节点，然后放到递归函数中判断。回溯的时候count+上当前的left/right节点。
    下面是C++,JAVA和Python代码。
    其中也用到了回溯，再理解一遍回溯思想。在处理左右节点的时候的函数。
count-=node->left->val;
if(traversal(node->left, count)) return true;
count += node->left->val;

我看弹幕上有人说：发现这条路径最后count不是0不符合条件的情况下，需要找到别的路径，这就需要退回去找。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     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:bool hasPathSum(TreeNode* root, int targetSum) {if(root){int count = targetSum-root->val;return traversal(root, count);}return false;}bool traversal(TreeNode* node, int count){if(node->left==NULL && node->right==NULL && count==0) return true;if(node->left==NULL && node->right==NULL && count!=0) return false;if(node->left){//要判断左孩子不为空否则递归左孩子的时候会出现空指针异常count-=node->left->val;if(traversal(node->left, count)) return true;count += node->left->val;}if(node->right){count-=node->right->val;if(traversal(node->right, count)) return true;count += node->right->val;}return false;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {boolean traversal(TreeNode node, int count){if(node.left==null && node.right==null && count==0) return true;if(node.left==null && node.right==null && count!=0) return false;if(node.left!=null){count-=node.left.val;if(traversal(node.left, count)) return true;//函数中最开始进行判断count+=node.left.val;//回溯}if(node.right!=null){count-=node.right.val;if(traversal(node.right, count)) return true;count+=node.right.val;}return false;}public boolean hasPathSum(TreeNode root, int targetSum) {if(root!=null){int count = targetSum-root.val;return traversal(root, count);}return false;}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if(root!=None):count=targetSum-root.valreturn self.traversal(root, count)return Falsedef traversal(self, node, count):if node.left==None and node.right==None and count==0:return Trueif node.left==None and node.right==None and count!=0:return False#说明这条路径不是if(node.left != None):count -= node.left.valif(self.traversal(node.left, count)):return Truecount += node.left.valif(node.right != None):count -= node.right.valif(self.traversal(node.right, count)):return Truecount += node.right.valreturn False

路径之和Ⅱ

在这里插入图片描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
与上一个相比要定义vector<vector> result;存储所有的路径，vector path;存储当前路径。
下面是C++，JAVA和Python代码。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     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:vector<vector<int>> result;vector<int> path;//递归函数不需要返回值，因为我们要遍历整个树void traversal(TreeNode* cur, int count){if(!cur->left && !cur->right && count == 0){//遇到了叶子节点，而且找到了和为targetSum的路径result.push_back(path);return;}if(!cur->left && !cur->right) return; //如果遇到叶子节点，没有合适的路径就直接返回if(cur->left){//左，防止遍历空节点path.push_back(cur->left->val);//从后面加入count -= cur->left->val;traversal(cur->left, count);//递归count += cur->left->val;//下面两个都是回溯，就是递归到这个节点和出这个节点的两种情况下环境不变path.pop_back();//从后面弹出}if(cur->right){//左，防止遍历空节点path.push_back(cur->right->val);//从后面加入count -= cur->right->val;traversal(cur->right, count);//递归count += cur->right->val;//下面两个都是回溯，就是递归到这个节点和出这个节点的两种情况下环境不变path.pop_back();//从后面弹出}return;}
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {result.clear();path.clear();if(root==NULL) return result;path.push_back(root->val);//把根节点放到路径traversal(root, targetSum - root->val);return result;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result; // 非空判断Deque<Integer> path = new LinkedList<>(); // 使用Dequepath.add(root.val);traversal(root, targetSum - root.val, result, path);return result;}public void traversal(TreeNode root, int count, List<List<Integer>> result, Deque<Integer> path) {if (root.left == null && root.right == null && count == 0) {result.add(new ArrayList<>(path));return;}if (root.left == null && root.right == null) return; // 这条路径不符合要求if (root.left != null) { // 左子树path.addLast(root.left.val);count -= root.left.val;traversal(root.left, count, result, path);count += root.left.val;path.pollLast();}if (root.right != null) { // 右子树path.addLast(root.right.val);count -= root.right.val;traversal(root.right, count, result, path);count += root.right.val;path.pollLast();}}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.result = []self.path = []def traversal(self, cur, count):if not cur.left and not cur.right and count == 0:#遇到了叶子节点而且找到了和为目标值的路径self.result.append(self.path[:])return if not cur.left and not cur.right:#遇到了叶子节点但是路径不符合条件returnif cur.left:#左 空节点不遍历self.path.append(cur.left.val)count-=cur.left.valself.traversal(cur.left, count)count += cur.left.valself.path.pop() #回溯if cur.right: #右 空节点不遍历self.path.append(cur.right.val)count -= cur.right.valself.traversal(cur.right, count) #递归count += cur.right.val #回溯self.path.pop() #回溯returndef pathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: List[List[int]]"""if not root:return self.resultself.path.append(root.val)self.traversal(root, targetSum - root.val)return self.result

参考文章

  1. https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

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

下面是C++代码。
主要的步骤有6个：

  1. 后序数组为0，说明是空节点。
  2. 后续数组最后一个元素为节点元素。
  3. 寻找中序数组位置找切割点。
  4. 切割中序数组。
  5. 切割后序数组。
  6. 递归处理左区间和右区间。
    在这里插入图片描述
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     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:
private: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] == root->val) break;}//切割中序数组//左中序区间左闭右开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()); }
};

参考文章

  1. https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【第七节】在RadAsm中使用OllyDBG调试器

【第七节】在RadAsm中使用OllyDBG调试器

前言 接着本专栏上一节&#xff0c;我们虽然已经用上RadAsm进行编写x86汇编代码并编译运行&#xff0c;但是想进行断点调试怎么办。RadAsm里面找不到断点调试&#xff0c;下面我们来介绍如何在RadAsm上联合调试器OllyDBG进行调试代码。 OllyDBG的介绍与下载 OllyDBG 是一款功能…
阅读更多...
WPF MVVM框架

WPF MVVM框架

一、MVVM简介 MVC Model View Control MVP MVVM即Model-View-ViewModel&#xff0c;MVVM模式与MVP&#xff08;Model-View-Presenter&#xff09;模式相似&#xff0c;主要目的是分离视图&#xff08;View&#xff09;和模型&#xff08;Model&#xff09;&#xff0c;具有低…
阅读更多...
PH热榜 | 2024-11-19

PH热榜 | 2024-11-19

DevNow 是一个精简的开源技术博客项目模版&#xff0c;支持 Vercel 一键部署&#xff0c;支持评论、搜索等功能&#xff0c;欢迎大家体验。 在线预览 1. Layer 标语&#xff1a;受大脑启发的规划器 介绍&#xff1a;体验一下这款新一代的任务和项目管理系统吧&#xff01;它…
阅读更多...
【ArcGISPro】使用AI模型提取要素-提取车辆（目标识别）

【ArcGISPro】使用AI模型提取要素-提取车辆（目标识别）

示例数据下载 栅格数据从网上随便找一个带有车辆的栅格数据 f094a6b1e205cd4d30a2e0f816f0c6af.jpg (1200799) (588ku.com) 添加数据
阅读更多...
联通光猫（烽火通信设备）改桥接教程

联通光猫（烽火通信设备）改桥接教程

一、获得超级密码 1.打开telnet连接权限 http://192.168.1.1/telnet?enable1&key9070D3BECD70&#xff08;MAC地址&#xff09;2.连接光猫获取密码 telnet 192.168.1.1 用户名&#xff1a;admin 密码&#xff1a;Fh9070D3BECD70连接成功后 load_cli factory show admin_…
阅读更多...
掌握SEO提升网站流量的关键在于长尾关键词的有效运用

掌握SEO提升网站流量的关键在于长尾关键词的有效运用

内容概要 在现代数字营销中&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;被广泛视为提升网站流量的核心策略之一&#xff0c;而其中长尾关键词的运用显得尤为重要。长尾关键词通常由三个或更多个词组成&#xff0c;具有更高的针对性和精确度&#xff0c;可以更好地满足…
阅读更多...
【期权懂｜个股期权中的备兑开仓策略是如何进行的？

【期权懂｜个股期权中的备兑开仓策略是如何进行的？

期权小懂每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 个股期权中的备兑开仓策略是如何进行的&#xff1f; 个股期权备兑开仓的优点和风险‌&#xff1a; ‌&#xff08;1&#xff09;优点‌&#xff1a;备兑开仓可以增强持股收益&…
阅读更多...
汽车安全再进化 - SemiDrive X9HP 与环景影像系统 AVM 的系统整合

汽车安全再进化 - SemiDrive X9HP 与环景影像系统 AVM 的系统整合

当今汽车工业正面临著前所未有的挑战与机遇&#xff0c;随著自动驾驶技术的迅速发展&#xff0c;汽车的安全性与性能需求日益提高。在这样的背景下&#xff0c;汽车 AVM&#xff08;Automotive Visual Monitoring&#xff09;标准应运而生&#xff0c;成为促进汽车智能化和安全…
阅读更多...
MongoDB聚合操作

MongoDB聚合操作

管道的聚合 管道在Unix和Linux中一般用于将当前命令的输出结果作为下一个命令的参数。 MongoDB的聚合管道将MongoDB文档在一个管道处理完毕后将结果传递给下一个管道处理。管道操作是可以重复的。 表达式&#xff1a;处理输入文档并输出。表达式是无状态的&#xff0c;只能用…
阅读更多...
向量数据库FAISS之五：原理(LSH、PQ、HNSW、IVF)

向量数据库FAISS之五：原理(LSH、PQ、HNSW、IVF)

1.Locality Sensitive Hashing (LSH) 使用 Shingling MinHashing 进行查找 左侧是字典&#xff0c;右侧是 LSH。目的是把足够相似的索引放在同一个桶内。 LSH 有很多的版本&#xff0c;很灵活&#xff0c;这里先介绍第一个版本&#xff0c;也是原始版本 Shingling one-hot …
阅读更多...
https(day30)

https(day30)

1.配置需要配置端口为443 2.配置需要配置证书 ssl_certificate /path/to/your/fullchain.pem; # 证书文件 ssl_certificate_key /path/to/your/private.key; # 私钥文件 3.其他优化
阅读更多...
【WPF】Prism学习（七）

【WPF】Prism学习（七）

Prism Dependency Injection 1.注册类型&#xff08;Registering Types&#xff09; 1.1. Prism中的服务生命周期&#xff1a; Transient&#xff08;瞬态&#xff09;&#xff1a;每次请求服务或类型时&#xff0c;都会获得一个新的实例。Singleton&#xff08;单例&#xf…
阅读更多...
服务器数据恢复—热备盘未激活导致硬盘掉线的raid5阵列崩溃的数据恢复案例

服务器数据恢复—热备盘未激活导致硬盘掉线的raid5阵列崩溃的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X3850服务器中有一组由数块SAS硬盘组建的RAID5阵列&#xff0c;该阵列中有一块盘是热备盘。操作系统为linux redhat&#xff0c;上面跑着一个基于oracle数据库的oa。 服务器故障&#xff1a; 服务器raid5阵列中有一块硬盘离线&#xff0…
阅读更多...
ADS 2022软件下载与安装教程

ADS 2022软件下载与安装教程

“ 本文以最新的Advanced Design System 2022为例介绍ADS软件的安装及crack教程 ” ADS 简介 先进设计系统 Advanced Design system&#xff08;ADS&#xff09;Agilent Technologies 是领先的电子设计自动化软件&#xff0c;适用于射频、微波和信号完整性应用。ADS 是获得商…
阅读更多...
Chrome 浏览器 131 版本新特性

Chrome 浏览器 131 版本新特性

Chrome 浏览器 131 版本新特性 一、Chrome 浏览器 131 版本更新 1. 在 iOS 上使用 Google Lens 搜索 自 Chrome 126 版本以来&#xff0c;用户可以通过 Google Lens 搜索屏幕上看到的任何图片或文字。 要使用此功能&#xff0c;请访问网站&#xff0c;并点击聚焦时出现在地…
阅读更多...
Unity 编辑器下 Android 平台 Addressable 加载模型粉红色，类似材质丢失

Unity 编辑器下 Android 平台 Addressable 加载模型粉红色，类似材质丢失

Unity 编辑器下 Android 平台 Addressable 加载模型粉红色&#xff0c;类似材质丢失 Addressable Play Mode Script加载模式 选择 Use Existiing Build 1.Unity 切换到 PC 平台&#xff0c;执行 Addressable Build 运行&#xff0c;加载 bundle 内的预制体 显示正常 2.Unit…
阅读更多...
独立站干货：WordPress主机推荐

独立站干货：WordPress主机推荐

WordPress作为全球最受欢迎的独立站建设平台&#xff0c;提供了灵活性和强大的功能&#xff0c;使得建站变得简单而高效。本文将为您详细介绍WordPress建站的流程&#xff0c;并推荐几款实测后觉得好用的主机商。 WordPress建站流程 域名注册 首先需要注册一个域名&#xff0c…
阅读更多...
每日OJ题_牛客_天使果冻_递推_C++_Java

每日OJ题_牛客_天使果冻_递推_C++_Java

目录 牛客_天使果冻_递推 题目解析 C代码 Java代码 牛客_天使果冻_递推 天使果冻 描述&#xff1a; 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻&#xff0c;但她想把最好吃的果冻留到最后收藏。天使想知道前 x个果冻中&#xff0c;美味…
阅读更多...
C++AVL平衡树

C++AVL平衡树

1.AVL平衡树节点定义 每一个节点都配左右孩子和父节点&#xff0c;以及平衡因子和其所对应的值。 template<class K, class V> struct AVLTreeNode {// 需要parent指针&#xff0c;后续更新平衡因子可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTr…
阅读更多...
Vue3 pinia使用

Vue3 pinia使用

Pinia 是一个现代的状态管理库&#xff0c;专为 Vue 3 设计。它提供了一种简单、直观的方式来管理应用中的全局状态 (就是不同组件都希望去共享的一些变量,函数等)。Pinia 的设计灵感来自于 Vuex&#xff08;Vue 2 的状态管理库&#xff09;&#xff0c;但进行了许多改进&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023