擅长:python、mysql、java
<p>基于kitt的解决方案,我在lintCode问题578上测试了他的解决方案,但是没有通过。该问题发生在计数条件下,应使用输入的两个节点再检查一次。因此,我重新设计了一个新的解决方案,它通过了lintcode测试,并且具有更好的读取逻辑。在</p>
<pre><code>"""
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.
"""
count = 0
def lowestCommonAncestor3(self, root, A, B):
result = self.lca(root, A, B)
return result if self.count == 2 else None
def lca(self, root, A, B):
if not root:
return None
for node in [A, B]:
if root == node:
self.count += 1
left = self.lca(root.left, A, B)
right = self.lca(root.right, A, B)
if root in (A, B) or left and right:
return root
if left:
return left
if right:
return right
return None
</code></pre>