当前位置:网站首页>235. 二叉搜索树的最近公共祖先【lca模板 + 找路径相同】
235. 二叉搜索树的最近公共祖先【lca模板 + 找路径相同】
2022-07-03 18:38:00 【白速龙王的回眸】
分析
找到root到p和q的路径(通过while和大小关系即可)
然后看看两条路径最深能到哪里相同
返回最深的相同的位置即可
ac code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 找到root到target的path
def get_path(start, target):
now = start
path = []
while now != target:
path.append(now)
# 下一层寻找
if target.val > now.val:
now = now.right
else:
now = now.left
path.append(target)
return path
pa = get_path(root, p)
pb = get_path(root, q)
ans = None
for u, v in zip(pa, pb):
if u == v:
ans = u
else:
break
return ans
总结
lca模板
边栏推荐
- How about the Moco model?
- Sensor 调试流程
- English语法_名词 - 分类
- [combinatorics] generating function (commutative property | derivative property | integral property)
- Valentine's day, send you a little red flower~
- 2022-2028 global plasmid DNA cdmo industry research and trend analysis report
- Computer graduation design PHP campus address book telephone number inquiry system
- 平淡的生活里除了有扎破皮肤的刺,还有那些原本让你魂牵梦绕的诗与远方
- NFT新的契机,多媒体NFT聚合平台OKALEIDO即将上线
- 简述服务量化分析体系
猜你喜欢
What kind of experience is it when the Institute earns 20000 yuan a month?
Golang string (string) and byte array ([]byte) are converted to each other
How does GCN use large convolution instead of small convolution? (the explanation of the paper includes super detailed notes + Chinese English comparison + pictures)
SQL injection -day16
English grammar_ Noun classification
Computer graduation design PHP sports goods online sales system website
Xception for deeplab v3+ (including super detailed code comments and original drawing of the paper)
What is SQL get connection
22.2.14 -- station B login with code -for circular list form - 'no attribute' - 'needs to be in path selenium screenshot deviation -crop clipping error -bytesio(), etc
论文阅读 GloDyNE Global Topology Preserving Dynamic Network Embedding
随机推荐
This diversion
Mature port AI ceaspectus leads the world in the application of AI in terminals, CIMC Feitong advanced products go global, smart terminals, intelligent ports, intelligent terminals
Computer graduation project PHP library book borrowing management system
圖像24比特深度轉8比特深度
How to track the real-time trend of Bank of London
Analysis of the reasons why enterprises build their own software development teams to use software manpower outsourcing services at the same time
Recent learning experience
PHP determines which constellation it belongs to today
VLAN experiment
Caddy server agent
Bidding procurement scheme management of Oracle project management system
Torch learning notes (6) -- logistic regression model (self training)
After nohup NPM start &, close the shell window directly, and the process closes accordingly
Boost. Asio Library
Common PostgreSQL commands
Image 24 bits de profondeur à 8 bits de profondeur
After the festival, a large number of people change careers. Is it still time to be 30? Listen to the experience of the past people
[combinatorics] generating function (example of using generating function to solve the number of solutions of indefinite equation)
2022-2028 global plasmid DNA cdmo industry research and trend analysis report
How does GCN use large convolution instead of small convolution? (the explanation of the paper includes super detailed notes + Chinese English comparison + pictures)