236 lowest common ancestor of a binary tree

236. Lowest Common Ancestor of a Binary Tree

Medium


class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
pathP = self.pathTo(root,p)
pathQ = self.pathTo(root,q)
n = min(len(pathP), len(pathQ))

ans = root
for i in range(n):
if pathP[i] == pathQ[i]:
ans = pathP[i]
else:
break
return ans

def pathTo(self, root, goal):
# goal node ,path
if root == None: return root
stack = [(root, [root])]
while stack:
node, path = stack.pop()
if node == goal:
return path
if node.left: stack.append((node.left, path + [node.left]))
if node.right: stack.append((node.right, path + [node.right]))



        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4


AC代码

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root == None:
return None

if p == root or q == root:
return root

left = self.lowestCommonAncestor(self.left,p,q)
right = self.lowestCommonAncestor(self.right,p,q)

if left and right:
return root

return left if left is None else right


apachecn/AiLearning