C++算法练习-day45——236.二叉树的最近公共祖先

news/2024/11/30 11:34:43/

题目来源:. - 力扣(LeetCode)

题目思路分析

题目要求在一个二叉树中找到两个给定节点的最低公共祖先(Lowest Common Ancestor, LCA)。最低公共祖先是指在树中同时包含两个给定节点的所有节点中,深度最大的那个节点。这意味着从该节点出发,能够同时到达这两个给定的节点。

思路

  1. 递归搜索:利用递归遍历树的每个节点,判断给定的两个节点是否在当前节点的左右子树中。
  2. 边界条件
    • 如果当前节点为空,或者当前节点就是给定的节点之一,直接返回当前节点。
    • 如果在左子树中找到了一个节点,而在右子树中没有找到另一个节点,则左子树的返回值即为LCA;反之亦然。
    • 如果在两个子树中都找到了这两个节点,那么当前节点即为LCA。

代码:

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */  
class Solution {  
public:  // 函数定义:找到p和q的最低公共祖先  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  // 边界条件:如果当前节点为空,或者当前节点就是p或q,返回当前节点  if(!root || root == p || root == q){  return root;  }  // 在左子树中递归查找p和q的LCA  TreeNode* left = lowestCommonAncestor(root->left, p, q);  // 在右子树中递归查找p和q的LCA  TreeNode* right = lowestCommonAncestor(root->right, p, q);  // 如果左子树返回null,说明p和q都在右子树中,返回右子树的结果  if(!left){  return right;  }  // 如果右子树返回null,说明p和q都在左子树中,返回左子树的结果  if(!right){  return left;  }  // 如果左右子树都不为空,说明p和q分别位于当前节点的左右两侧,当前节点即为LCA  return root;  }  
};

知识点摘要

  1. 二叉树的基本概念:节点、左子树、右子树、根节点等。
  2. 递归算法:通过函数调用自身来解决问题,特别适合树结构的问题。
  3. 边界条件处理:在递归中处理各种可能的边界情况,确保算法的正确性。

通过本题,我们学会了如何在二叉树中利用递归方法找到两个节点的最低公共祖先。这种方法的核心在于通过递归遍历树的每个节点,并判断给定的两个节点是否在当前节点的左右子树中。根据这个判断,我们可以确定当前节点是否是LCA。本题不仅考察了对二叉树的理解,还考察了递归算法的应用以及边界条件的处理。希望读者能够通过本题加深对二叉树和递归算法的理解,并在未来的编程实践中灵活运用这些知识。


http://www.ppmy.cn/news/1551185.html

相关文章

记一次 .NET某hdp智能柜系统 卡死分析

一:背景 1. 讲故事 停了一个月时间没有更新博客了,主要是这段时间有些许事情导致心神不宁,我这个人也比较浮躁所以无法潜心修炼,事情如下: 被狗咬了 也不知道是不是出门没看黄历,在小区门口店里买烟&am…

【Story】《嵌入式开发中的Bug故事:挑战、解决与成长》

作为一名嵌入式高级工程师,编写高效、稳定的嵌入式系统是我们的核心任务。然而,程序的世界里,Bug就像潜伏在阴影中的敌人,时刻可能以各种方式出现,打破我们精心设计的系统,带来无法预见的麻烦。作为嵌入式系…

你真的会用饼图吗?JVS-智能BI饼图组件深度解析

在数据可视化的世界里,饼图是我们常见的一种可视化图形。在JVS-智能BI中提供了数据可视化饼图组件,接下来我通过这篇文章详细介绍,从配色方案到图形配置,从显示数据到提示信息,饼图的每一个细节配置。 饼图类图表概述…

云计算基础-期末复习

第一章:云计算概论 一、云计算的定义与特征 1. 定义: 云计算是一种通过网络以按需、可扩展的方式获取计算资源和服务的模式。它将计算资源视为一种公用事业,用户可以根据需求动态获取和释放资源,而无需了解底层基础设施的细节。…

USB Type-C一线通扩展屏:多场景应用,重塑高效办公与极致娱乐体验

在追求高效与便捷的时代,启明智显USB Type-C一线通扩展屏方案正以其独特的优势,成为众多职场人士、娱乐爱好者和游戏玩家的首选。这款扩展屏不仅具备卓越的性能和广泛的兼容性,更能在多个应用场景中发挥出其独特的价值。 USB2.0显卡&#xff…

【特斯拉的自动驾驶好在哪】

虽然特斯拉的自动驾驶目前处于 L2 级别,但在自动驾驶的评选中排名相对较高,主要有以下原因: 技术创新与硬件优势 强大的芯片研发能力:特斯拉自主研发的 FSD 芯片算力高达 72Tops,板卡为 144Tops,相较于英…

Python设计模式详解之15 ——迭代器模式

Python 中的 Iterator(迭代器)设计模式 是一种行为型设计模式,用于逐一访问集合对象中的元素而不暴露其底层实现。Python 本身对迭代器模式提供了良好的支持,迭代器通常通过 __iter__ 和 __next__ 方法实现。 迭代器模式的组成 迭…

[网络安全]sqli-labs Less-5 解题详析

判断注入类型 GET1 and 11 回显如下:GET1 and 12没有回显,说明该漏洞类型为GET型单引号字符型注入 判断注入点个数 GET1 order by 3 --,回显如下:GET1 order by 4 --,回显如下:故注入点为3个 该题若查询…