题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 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。因为根据定义最近公共祖先节点可以为节点本身。 说明:
解题思路
由上向下的思路
在DFS递归的过程中, 判断以当前结点为根节点的树中都有哪些节点, 找到第一个包含p和q的节点, 就是要找的最近公共祖先节点.
使用哈希表存储每个节点代表的树中包含的所有节点.
复制 # 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':
def dfs(node):
if node is None:
return False, set(), None
node_set = set([node])
left_status, left_set, parnet = dfs(node.left)
if left_status:
return left_status, left_set, parnet
node_set = node_set.union(left_set)
if p in node_set and q in node_set:
return True, node_set, node
right_status, right_set, parnet = dfs(node.right)
if right_status:
return right_status, right_set, parnet
node_set = node_set.union(right_set)
if p in node_set and q in node_set:
return True, node_set, node
return False, node_set, None
_, _, p = dfs(root)
return p 由下向上的思路
构建一个函数, 返回的内容是候选的最近公共祖先 结点.
首先, 一个节点root如果是p和q的最近公共祖先, 则只可能是以下几种情况:
p和q分别在root的左右子树中, 不能在同一侧子树中
因此, DFS使用的递归函数在遇到p或q时, 就无需继续向下遍历, 可以开始向上回溯了. 因为节点p或q满足上面的第二, 第三条, 如果真实情况就是q在p为根节点的子树中, 或反过来, 那么这个节点就是最近公共祖先节点.
在回溯的过程中, 根据左子树left和右子树right的返回, 有四种情况:
left和right同时为None, 说明root的左右子树都不包含p和q, 继续向上返回None
left和right都不为空, 说明p和q分别在root的不同侧, 因此root是最近公共祖先节点, 返回root
left为空, right不为空, 直接返回right
可能是right中只有p, 没有q(或只有q), 此时的right是指向p为根节点的
可能right中包含p和q节点, 此时的right是指向最近公共祖先节点的
left不为空, right为空, 返回left, 具体情况同第三种情况
还有一个边际情况是遇到了空节点, 直接返回None就可以.
复制 # 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:
def dfs(node):
if not node or node is p or node is q:
return node
left = dfs(node.left)
right = dfs(node.right)
if not left:
return right
if not right:
return left
return node
return dfs(root) 