1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
# 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 visit(self, root, cur_path, pathes, p, q): if root == None: return cur_path.append(root) if root==p: pathes.append(cur_path[:]) if root==q: pathes.append(cur_path[:]) self.visit(root.left, cur_path, pathes, p, q) self.visit(root.right, cur_path, pathes, p, q) cur_path.pop()
def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root == None: return None pathes = [] self.visit(root, [], pathes, p, q) i = 0 while i < min(len(pathes[0]),len(pathes[1])): if pathes[0][i] != pathes[1][i]: break i += 1 return pathes[0][i-1]
|
近期评论