236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

思路：

1. 找到p、q节点的路径
2. 路径中最后一个相同元素就是最近公共祖先的值，如root=3 p=5 q=1，两个路径[3,5] [3,1]，公共祖先的值就是最后一个相同元素【3】
3. 再遍历一次二叉树，用这个元素找到对应节点返回

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# p、q节点路径保存到2个列表中，这两个列表中最后一个相同元素即是最近公共祖先self.result = [] # 记录所有根节点到叶子节点的路径self.cur_path = [] # 当前路径self.traverse(root, p, q)# 找到两个列表中最后一个相同元素result_val = Nonefor i in range(min(len(self.result[0]),len(self.result[1]))):if self.result[0][i] == self.result[1][i]:result_val = self.result[0][i]# 找到result_val对应的节点然后returnself.result_node = rootself.traverse2(root, result_val)return self.result_nodedef traverse(self, cur_node, p, q):# 遍历二叉树，找到二叉树路径if not cur_node:return self.cur_path.append(cur_node.val)if p.val == cur_node.val or q.val == cur_node.val:self.result.append(self.cur_path[:])self.traverse(cur_node.left, p, q)self.traverse(cur_node.right, p, q)# 往回返的时候要从self.path中拿掉 因为既然回去了 就不能算走过的路径了 self.cur_path.pop()def traverse2(self, cur_node, result_val):if not cur_node:return if cur_node.val == result_val:self.result_node = cur_nodeself.traverse2(cur_node.left, result_val)self.traverse2(cur_node.right, result_val)