# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
#either our function reached a leaf node, or encountered one of the node, carry it back out in either left or right variable, and wait for the other node to be found.
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
#recursively look for each node in the subtrees, once we found both nodes, return the immediate root. otherwise, return the node found, and recursive back until we find the other node.
return root if （left and right） else （left or right）
236. Lowest Common Ancestor of a Binary Tree
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 采用递归，分别在左子树和右子树里面查找，如果都能找到，当前节点就是最近共同祖先如果只能在一个树找到，说明这个数就是...
- 求两个节点最近的祖先节点，思路是找到根节点到所求节点的路径，那么两条路径分叉处就是祖先节点递归，假定root不是p...
- 任意二叉树的两个结点的最小公共祖先。 思路：两个结点一定满足，在他们父结点的两端（如果两个结点本身不是父结点）。 代码：
- Question Given a binary tree, find the lowest common ance...
- 原题 给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度...
