题目描述
236. 二叉树的最近公共祖先 剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 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 由下向上的思路
236. 二叉树的最近公共祖先（后序遍历 DFS ，清晰图解） 【C++ 经典递归】思路非常好理解 时间复杂度O(n), 空间复杂度O(n)
构建一个函数, 返回的内容是候选的最近公共祖先 结点.
首先, 一个节点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)