对于这个题我们可以用深度优先遍历分别找到从根节点到两个所比价的节点的路径，然后比较得到的路径，求出最先不同的那个节点之前的那个节点即可。这个算法的时间复杂度是O（N），空间复杂度最差情况下是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
path_p, path_q = [], []
def traversal(node, target, path):
if not node:
return False
path.append(node)
if node.val == target.val:
return True
if traversal(node.left, target, path) or traversal(node.right, target, path):
return True
path.pop()
traversal(root, p, path_p)
traversal(root, q, path_q)
i = 0
while i < len(path_q) and i < len(path_p) and path_q[i] == path_p[i]:
res = path_p[i]
i += 1
return resPREVIOUSlc008.把字符串转换成整数