题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类
# @param o1 int整型
# @param o2 int整型
# @return int整型
#
class Solution:
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
if root is None:
return root.val
if left:
return left
if right:
return right
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 思路：两种情况：最近公共祖先不为所找结点和为所找结点。若根节点不为找的结点，且其左右子树中分别有所找结点，则此根节点为最近公共祖先；若根节点为找的结点，且另一个节点在其子树中，则此根节点为最近公共祖先；
# 方法：使用递归的方法递归根节点的左右子树，使用先序的方法，先判断根节点是否为所找结点，若不为节点则继续递归其左右子树，直到最底层返回None；若某根节点为所找结点，不再继续递归，返回此根节点的值到上一层的左或右子节点。判断（从下往上）根节点左右子树的返回值，若左右子树都不为None，则返回此根节点；若左子树不为None，右子树为None，则返回左子树的返回值；若右子树不为None，左子树为None，则返回右子树的返回值。
##
# @param root TreeNode类
# @param o1 int整型
# @param o2 int整型
# @return int整型
#
class Solution:
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
if root is None:
return None
# 先序从上往下判断根节点是否为所找结点
if root.val == o1 or root.val == o2:
return root.val
# 递归左右子树
left = self.lowestCommonAncestor(root.left, o1, o2)
right = self.lowestCommonAncestor(root.right, o1, o2)
# 从底层往上判断根节点的左右子树
if left and right:return root.val
if left:
return left
if right:
return right