面试题68 - II. 二叉树的最近公共祖先
2024-08-24 12:16:50
<搜索树结点>
<获取路径>
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。
因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
注意:本题与主站 236 题相同:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
我的思路
1. 定义 dfs(self , node , tar , path) 为在树中找到目标结点(tar),并储存从根结点到目标结点的路径(path)
2. 找到结点 p 的路径 path_p ,结点 q 的路径 path_q
3. 从尾到头比较路径 path_p 、 path_q,返回相等的那个结点
* 一定会有相同的结点,最坏的情况相同的结点是根结点
class Solution(object):
def __init__(self):
self.ret = 0
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
path_p,path_q = [],[]
self.dfs(root,p,path_p)
self.dfs(root,q,path_q)
ls = min(len(path_p),len(path_q))-1 while ls>=0:
if path_p[ls] == path_q[ls]:
return path_p[ls]
ls-=1 def dfs(self,root,tar,path):
if not root:
return False path.append(root.val) if root.val == tar.val:
return True
ans1 = self.dfs(root.left,tar,path)
ans2 = self.dfs(root.right,tar,path)
# 搜到叶子节点,没找到,则原路返回,把路上的结点pop出去
if not ans1 and not ans2:
path.pop()
return ans1 or ans2
总结
1. 在一棵树中搜索目标结点
2. 深搜获取根节点到目标结点的路径
最新文章
- Linux安装脚本需要交互之如何实现自动安装
- man 在线手册
- 寻找Linux单机负载瓶颈
- 向CodeBlocks的Project中添加calss文件时,出现No such file or directory错误的解决方案
- C# winform 最小化到电脑右下角
- C# 产生随机密码
- NOIP2015 斗地主(搜索+剪枝)
- 【HDOJ】3466 Proud Merchants
- Hibernate学习笔记-Hibernate HQL查询
- 【深搜加剪枝】【HDU1455】【Sticks】
- devexpress中用ChartControl生成柱状图
- PyCharm 教程
- 10年java过来人聊聊自己的自学、培训和工作经历
- C. Polycarp at the Radio
- 毕加索的艺术——Picasso,一个强大的Android图片下载缓存库,OkHttpUtils的使用,二次封装PicassoUtils实现微信精选
- pyspider安装提示:got an unexpected keyword argument &#39;io_loop&#39;的解决办法
- SecureCRT通过拷贝配置文件登陆
- C# 创建 写入 读取 excel
- VirtualBox 安装 CentOS6.5 教程
- spring-boot 速成(10) -【个人邮箱/企业邮箱】发送邮件
热门文章
- RPC、HTTP、RESTful
- 注解开发中的@Results注解使用
- java上传图片或文件
- 常用windows命令和Dos命令
- Docker(4)-docker常用命令
- MySQL获取对应时间
- 07- Vue3 UI Framework - Switch 组件
- 多个工作簿拆分(Excel代码集团)
- 当是class com.cosl.po.Pc$$EnhancerByCGLIB$$38c58f03时,反射属性都他妈不好用了
- .net Core 使用 iTextSharp 生成PDF 简单示例