236. Lowest Common Ancestor of a Binary Tree
My solution exceed time limit:
python
# 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':
ans = {root: 0}
def isAncestor(root, d):
if not root:
return False
# dfs 判断node在不在root的树中
def dfs(root, node):
if not root:
return False
if root is node:
return True
return dfs(root.left, node) or dfs(root.right, node)
f = dfs(root, p) and dfs(root, q)
if f == True:
d > max(ans.values())
ans[root] = d
# isAncestor 向下递归root
isAncestor(root.left, d+1)
isAncestor(root.right, d+1)
return f
isAncestor(root, 0)
a = {x: i for i, x in ans.items()}
return a[max(a.keys())]根据以上定义，若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
- p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
- p=root ，且 q 在 root 的左或右子树中；
- q=root ，且 p 在 root 的左或右子树中；
二叉树最近公共祖先——递归解析
思路
通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当 p, q 在当前节点 root 的异侧时，root 即为最近公共祖先，向上返回 root。
1. 终止条件
- 当越过叶节点
- 当
root == null时，直接返回null
- 当
- 找到目标节点
- 当
root == p或root == q时，直接返回root
- 当
2. 递推工作
- 递归调用左子树，返回值记为
left - 递归调用右子树，返回值记为
right
3. 根据 left 和 right 的情况返回结果
left和right同时为空- 说明
root的左右子树都不包含p, q - 返回
null
- 说明
left和right同时不为空- 说明
p, q分别在root的左、右子树 - 因此当前
root就是最近公共祖先，返回root
- 说明
left为空，right不为空- 说明
p, q不在root的左子树中，直接返回right - 细分两种情况：
- 只有
p或q（假设为p）在右子树，此时right指向p p, q都在右子树，此时right指向它们的最近公共祖先
- 只有
- 说明
left不为空，right为空- 同理，说明
p, q都不在右子树，直接返回left
- 同理，说明
作者：Krahets 链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/240096/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
python
# 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':
# 只要当前根节点是p和q中的任意一个，就返回（因为不能比这个更深了，再深p和q中的一个就没了）
if not root or root == p or root == q:
return root
# 根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q
# left和right为 p 或者 q 或者 None
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# p和q都没找到，那就没有
if left == None and right == None:
return None
# 左子树没有p也没有q，就返回右子树的结果
if left == None:
return right
# 右子树没有p也没有q就返回左子树的结果
if right == None:
return left
# 左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
return root