当前位置:网站首页>剑指Offer 68 - II. 二叉树的最近公共祖先
剑指Offer 68 - II. 二叉树的最近公共祖先
2022-07-04 22:20:00 【LuZhouShiLi】
剑指 Offer 68 - II. 二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路
- 如果P和Q都是root的左右节点,那么root就是我们要找的最近公共祖先
- 如果P和Q都是root的左节点,那么返回lowestCommonAncestor(root.left,p,q)
- 如果P和Q都是root的右节点,那么返回lowestCommonAncestor(root.right,p,q)
边界条件讨论:
- 如果root = null 说明找不到,如果root = p或者root = q,返回root
- 如果左子树没找到,递归函数返回null,证明p和q都是在同测,那么就在右子树中查找
- 如果右子树没找到,递归函数返回null,证明p和q都是在同测,那么就在左子树中查找
代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q)
{
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode == null)
{
return rightNode;
}
if(rightNode == null)
{
return leftNode;
}
return root;
}
}
边栏推荐
- Summary of index operations in mongodb
- Scala download and configuration
- 共创软硬件协同生态:Graphcore IPU与百度飞桨的“联合提交”亮相MLPerf
- SQL中MAX与GREATEST的区别
- Apachecn translation, proofreading, note sorting activity progress announcement 2022.7
- 记录:关于Win10系统中Microsoft Edge上的网页如何滚动截屏?
- leetcode 72. Edit Distance 编辑距离(中等)
- Alibaba launched a new brand "Lingyang" and is committed to becoming a "digital leader"
- [cooking record] - stir fried 1000 pieces of green pepper
- Detailed explanation of flask context
猜你喜欢
2022-07-04: what is the output of the following go language code? A:true; B:false; C: Compilation error. package main import “fmt“ func main() { fmt.Pri
30余家机构联合发起数字藏品行业倡议,未来会如何前进?
Google Earth Engine(GEE)——基于 MCD64A1 的 GlobFire 日常火灾数据集
攻防世界 MISC 进阶 glance-50
MySQL Architecture - logical architecture
醒悟的日子,我是怎么一步一步走向软件测试的道路
UML图记忆技巧
Concurrent optimization summary
攻防世界 MISC 进阶区 3-11
The Sandbox 和数字好莱坞达成合作,通过人力资源开发加速创作者经济的发展
随机推荐
攻防世界 MISC 进阶区 3-11
醒悟的日子,我是怎么一步一步走向软件测试的道路
Alibaba launched a new brand "Lingyang" and is committed to becoming a "digital leader"
LOGO特訓營 第一節 鑒別Logo與Logo設計思路
攻防世界 MISC 高手进阶区 001 normal_png
攻防世界 MISC 进阶区 Erik-Baleog-and-Olaf
The new version judges the code of PC and mobile terminal, the mobile terminal jumps to the mobile terminal, and the PC jumps to the latest valid code of PC terminal
Common shortcut keys for hbuilder x
Close system call analysis - Performance Optimization
Logo special training camp section II collocation relationship between words and graphics
MySQL Architecture - user rights and management
【愚公系列】2022年7月 Go教学课程 003-IDE的安装和基本使用
Common open source codeless testing tools
Interview essential leetcode linked list algorithm question summary, whole process dry goods!
嵌入式开发:技巧和窍门——提高嵌入式软件代码质量的7个技巧
Google Earth Engine(GEE)——基于 MCD64A1 的 GlobFire 日常火灾数据集
如何实现轻松管理1500万员工?
Locust performance test - environment construction and use
攻防世界 MISC 进阶区 hong
sobel过滤器