LeetCode-236-二叉树的最近公共祖先

原题链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

image.png
image.png

解题思路：

1. 用字典来存储节点及其父节点，即递归遍历一次树，字典的key为子节点，value为父节点；
2. 以节点p为起点，向root节点遍历，用字典或者set存储遍历过的节点，即节点p的各个父节点，包括p本身；
3. 再以节点q为起点，向root节点遍历，相当于遍历q节点的各个父节点，遇到的第一个在p父节点集合中的节点，即为最深的公共父节点。

Python3代码：

# 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':
        node_dict = {}
        node_dict[root] = None
        def dfs(root):
            if root.left:
                node_dict[root.left] = root
                dfs(root.left)
            if root.right:
                node_dict[root.right] = root
                dfs(root.right)
        dfs(root) # 存储各节点映射的父节点
        visited = {}
        while p:
            visited[p] = True  # 存储p节点本身及p的父节点
            p = node_dict[p] 
        while q:  # 自q向root遍历
            if q in visited: 
                return q
            q = node_dict[q]
        return None