LintCode 578. 最近公共祖先 III
题目描述
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
返回 null 如果两个节点在这棵树上不存在最近公共祖先的话。
这两个节点未必都在这棵树上出现。
每个节点的值都不同
测试样例
输入:
{4, 3, 7, #, #, 5, 6}
3 5
5 6
6 7
5 8
输出:
4
7
7
null
解释:
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
输入:
{1}
1 1
输出:
1
说明：
这棵树只有一个值为1的节点
解题思路
1、分冶
分别从左、右子树去寻找A、B与LCA， 每棵子树返回三个结果，分别代表是否发现了A、B以及找到的LCA，记左、右子树的返回结果分别为lA、lB、l_LCA 和 rA、rB、r_LCA；
得到左、右子树的处理结果后，若A、B是在不同子树下发现的，则当前节点必定是LCA，直接返回；
否则，若有其中一颗子树发现了A（B）或者当前节点即A（B），则代表发现了A（B），同时，将LCA设为左子树或右子树返回的LCA；进一步判断，若在当前节点下A、B都被发现了，且当前节点是A或B，则将LCA设为当前节点。
2、DFS then Common Route
使用DFS做遍历，在遍历过程中记录A、B的公共路径，每遍历到一个节点就将其加入到公共路径中；
若遍历到A/B，则设置A/B的路径为当前的公共路径；
若A和B的路径都已设置完毕，则无需再遍历；
每次DFS的最后，要判断下A和B的路径是否同时为空，若是，则需要将此次加入的节点从公共路径中删除，因为其不在A和B的公共路径中。
3、设置父节点，比较公共祖先
为每个节点设置父节点属性，然后判断下A、B是否存在该属性，若有其一不存在父节点属性，则说明其不在这棵树中，直接返回；
否则，从A开始递归，将其所有祖先加入到列表中（包括自己）；
然后从B开始递归至其所有祖先，若递归到某个节点出现在A的祖先列表中，则代表其是LCA，直接返回；
最后，若以上步骤未求得接，返回None。
代码
1、分冶
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary tree.
@param: A: A TreeNode
@param: B: A TreeNode
@return: Return the LCA of the two nodes.
"""
def lowestCommonAncestor3(self, root, A, B):
_, _, LCA = self.helper(root, A, B)
return LCA
def helper(self, node, A, B):
"""返回是否发现了A、B以及当前找到的LCA"""
if not node:
return False, False, None
lA, lB, l_LCA = self.helper(node.left, A, B)
rA, rB, r_LCA = self.helper(node.right, A, B)
# 如果A、B是在不同子树下找到的，
# 那么当前节点就是LCA
if (lA and rB) or (rA and lB):
return True, True, node
find_A = lA or rA or node == A
find_B = lB or rB or node == B
LCA = l_LCA or r_LCA
# 如果A、B在子树中（不管是否同一子树）找到了，
# 且当前节点就是A或B，那么当前节点绝对是LCA
if find_A and find_B and (node == A or node == B):
LCA = node
return find_A, find_B, LCA
2、DFS then Common Route
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary tree.
@param: A: A TreeNode
@param: B: A TreeNode
@return: Return the LCA of the two nodes.
"""
def lowestCommonAncestor3(self, root, A, B):
# A、B的公共路径
self.route_AB = []
# A的路径
self.route_A = []
# B的路径
self.route_B = []
self.dfs(root, A, B)
# 说明A/B不在树中
if not (self.route_A and self.route_B):
return None
# 注意要反转顺序，否则直接返回根节点
self.route_AB.reverse()
for node in self.route_AB:
if node in self.route_A and node in self.route_B:
return node
return None
def dfs(self, node, A, B):
if not node:
return
self.route_AB.append(node)
if node == A:
self.route_A = [n for n in self.route_AB]
if node == B:
self.route_B = [n for n in self.route_AB]
# 如果A、B的路径都找到了，就无需往深处遍历了
if self.route_A and self.route_B:
return
self.dfs(node.left, A, B)
self.dfs(node.right, A, B)
# 因为route_AB代表的是A和B的公共路径
# 若当前节点遍历完但A、B仍有其一路径
# 未构造，则说明当前节点不是A、B的公共部分
# 所以将其在route_AB弹出
if not (self.route_A and self.route_B):
self.route_AB.pop()
3、设置父节点，比较公共祖先
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary tree.
@param: A: A TreeNode
@param: B: A TreeNode
@return: Return the LCA of the two nodes.
"""
def lowestCommonAncestor3(self, root, A, B):
self.set_parent(root, None)
# 若A/B没有父节点，说明它们不在这棵树中，返回None
if not (hasattr(A, 'parent') and hasattr(B, 'parent')):
return None
# 将A的所有祖先（包括自己）加入列表
parents = [A]
node = A.parent
while node:
parents.append(node)
node = node.parent
# 从B开始递归它的所有祖先（包括自己）
# 看是否在A的祖先们中
node = B
while node:
if node in parents:
return node
node = node.parent
return None
def set_parent(self, node, parent):
"""为每个节点设置父节点"""
if not node:
return
node.parent = parent
self.set_parent(node.left, node)
