ea账号注册网址,seo网站课程,常见的网络营销方法有哪些,个人网站备案做商城原题链接#x1f517;#xff1a;二叉树的最近公共祖先 难度#xff1a;中等⭐️⭐️
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点…原题链接二叉树的最近公共祖先 难度中等⭐️⭐️
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
示例 1
输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2
输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3
输入root [1,2], p 1, q 2 输出1
提示
树中节点数目在范围 [2, 105] 内。-109 Node.val 109所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。
二叉树最近公共祖先 在二叉树中找到两个节点的最近公共祖先Lowest Common Ancestor, LCA是一个常见的算法问题。最近公共祖先是指在二叉树中能够同时包含两个给定节点的最低即最深的节点。以下是解决这个问题的一般步骤和考虑因素 理解问题你需要找到两个给定节点在二叉树中的LCA。 递归方法递归是解决这个问题的常用方法。你可以从根节点开始递归地搜索两个节点。 基本情况 如果当前节点为空返回空。如果当前节点等于其中一个给定节点返回当前节点。 递归搜索 在当前节点的左子树和右子树中递归地搜索两个节点。 合并结果 如果在左子树中找到了一个节点在右子树中也找到了另一个节点那么当前节点就是LCA。如果只在左子树或右子树中找到了一个节点那么LCA就是这个子树中的节点。如果两个子树都为空那么当前节点不是LCA的一部分。 实现使用递归函数实现上述逻辑。 测试确保你的解决方案可以处理各种情况包括但不限于 二叉树只有一个节点。两个节点在不同的分支上。两个节点在相同的分支上。两个节点中的一个或两个都是根节点。 优化考虑算法的时间复杂度和空间复杂度。递归方法的时间复杂度通常是O(N)其中N是树中节点的数量空间复杂度取决于树的高度最坏情况下是O(N)。 题解
解题思路 LeetCode 上的 “二叉树的最近公共祖先 III” 题目要求解决的是在二叉树中找到两个节点的最近公共祖先LCA。这个问题可以通过递归的方式来解决下面是解题的一般思路 定义问题给定两个值找到二叉树中包含这两个值的最近公共祖先。 理解二叉树二叉树是一种特殊的树形数据结构其中每个节点最多有两个子节点。 递归方法 递归函数将接收当前节点和两个值作为参数。如果当前节点为空返回空。检查当前节点是否等于两个值中的任意一个如果是返回当前节点。递归地在左子树和右子树中查找这两个值。 处理递归结果 如果左子树和右子树都为空说明当前节点的子树中没有找到两个值返回空。如果左子树和右子树都非空说明两个值分别在左右子树中当前节点就是它们的LCA返回当前节点。如果只有一个子树非空说明两个值都在一个子树中继续在该子树中查找LCA c demo
#include iostream
#include vectorstruct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点为空或者等于p或q返回当前节点if (!root || root p || root q) {return root;}// 递归地在左子树和右子树中查找p和qTreeNode* left lowestCommonAncestor(root-left, p, q);TreeNode* right lowestCommonAncestor(root-right, p, q);// 如果左右子树都为空说明p和q都不在当前节点的子树中if (!left !right) {return nullptr;}// 如果左右子树中只有一个为空说明p和q都在非空的子树中if (left !right) {return left;}if (!left right) {return right;}// 如果左右子树都不为空说明p在一边q在另一边当前节点是它们的LCAreturn root;}
};int main() {// 构建示例二叉树// 2// / \// 3 5// / \ \// 1 4 6TreeNode* root new TreeNode(2);root-left new TreeNode(3);root-right new TreeNode(5);root-left-left new TreeNode(1);root-left-right new TreeNode(4);root-right-right new TreeNode(6);// 创建两个节点TreeNode* p root-left-left; // 值为1的节点TreeNode* q root-right-right; // 值为6的节点// 创建Solution对象并调用函数Solution solution;TreeNode* lca solution.lowestCommonAncestor(root, p, q);// 打印结果if (lca) {std::cout LCA of p-val and q-val is lca-val std::endl;}else {std::cout No common ancestor found. std::endl;}// 清理内存delete root-left-left;delete root-left-right;delete root-right-right;delete root-left;delete root-right;delete root;return 0;
}输出结果 LCA of 1 and 6 is 2
