Leetcode 236. Lowest Common Ancestor of a Binary Tree

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Lowest Common Ancestor of a Binary Tree

2. Solution

思路:分别搜索p, q结点,保存搜索路径(逆序),比较路径中第一个相同的结点即为二者的最低共同祖先节点。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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':
if root.val == p.val or root.val == q.val:
return root
p_path = []
q_path = []
self.dfs(root, p, p_path)
self.dfs(root, q, q_path)
for temp in p_path:
if temp in q_path:
return temp
def dfs(self, root, target, result):
if root is None:
return False
if root.val == target.val:
result.append(root)
return True
if self.dfs(root.left, target, result) or self.dfs(root.right, target, result):
result.append(root)
return True
else:
return False

Reference

  1. https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
如果有收获,可以请我喝杯咖啡!