LeetCode(算法)- 236. 二叉树的最近公共祖先

简介: LeetCode(算法)- 236. 二叉树的最近公共祖先

题目链接:点击打开链接

题目大意:

解题思路:

相关企业

  • 字节跳动
  • Facebook
  • 亚马逊(Amazon)
  • 谷歌(Google)
  • 微软(Microsoft)
  • 苹果(Apple)
  • 领英(LinkedIn)
  • PayPal

AC 代码

  • Java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/// 解决方案(1)classSolution {
Queue<TreeNode>pQue=newLinkedList<>(), qQue=newLinkedList<>();
Map<TreeNode, Integer>pMap=newHashMap<>(), qMap=newHashMap<>();
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
dfs(root, p.val, pQue, pMap, 0);
dfs(root, q.val, qQue, qMap, 0);
TreeNoderes=common();
returnres;
    }
TreeNodecommon() {
TreeNoderes;
while (!pQue.isEmpty() &&!qQue.isEmpty()) {
TreeNodepe=pQue.peek();
TreeNodeqe=qQue.peek();
if (pe.val==qe.val) {
res=pQue.peek();
pQue.poll();
qQue.poll();
returnres;
            }
if (pMap.get(pe) >qMap.get(qe)) {
pQue.poll();
            } elseif (pMap.get(pe) <qMap.get(qe)) {
qQue.poll();
            } else {
pQue.poll();
qQue.poll();
            }
        }
returnnull;
    }
booleandfs(TreeNodenode, intval, Queue<TreeNode>queue, Map<TreeNode, Integer>map, intl) {
if (node==null) {
returnfalse;
        }
if (node.val==val) {
queue.offer(node);
map.put(node, l);
returntrue;
        }
booleanleft=dfs(node.left, val, queue, map, l+1);
if (left) {
queue.offer(node);
map.put(node, l);
returntrue;
        }
booleanright=dfs(node.right, val, queue, map, l+1);
if (right) {
queue.offer(node);
map.put(node, l);
returntrue;
        }
returnfalse;
    }
}
// 解决方案(2)classSolution {
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
if(root==null||root==p||root==q) returnroot;
TreeNodeleft=lowestCommonAncestor(root.left, p, q);
TreeNoderight=lowestCommonAncestor(root.right, p, q);
if(left==null) returnright;
if(right==null) returnleft;
returnroot;
    }
}
  • C++
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/classSolution {
public:
TreeNode*lowestCommonAncestor(TreeNode*root, TreeNode*p, TreeNode*q) {
if(root==nullptr||root==p||root==q) returnroot;
TreeNode*left=lowestCommonAncestor(root->left, p, q);
TreeNode*right=lowestCommonAncestor(root->right, p, q);
if(left==nullptr) returnright;
if(right==nullptr) returnleft;
returnroot;
    }
};
目录
相关文章
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
268 14
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
134 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
152 10
|
6月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
283 10
|
6月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
299 9
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
210 10
 算法系列之数据结构-二叉树
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
289 3
|
21天前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
137 3
|
26天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
15天前
|
机器学习/深度学习 算法 数据可视化
基于MVO多元宇宙优化的DBSCAN聚类算法matlab仿真
本程序基于MATLAB实现MVO优化的DBSCAN聚类算法,通过多元宇宙优化自动搜索最优参数Eps与MinPts,提升聚类精度。对比传统DBSCAN,MVO-DBSCAN有效克服参数依赖问题,适应复杂数据分布,增强鲁棒性,适用于非均匀密度数据集的高效聚类分析。

热门文章

最新文章