Leetcode题236、二叉树的最近公共祖先（Python题解）Facebook面试题

问题：

题目来源：力扣（LeetCode）

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

难度：中等

分析： 递归理解的一道经典题目。 思路一：递归

首先写终止条件，没找到节点，返回空。然后写，如果找到指定节点了，需要终止，并回传节点。

回传节点特别重要，当遇到某个父节点接受到来自left和right的回传值，那么就更新回传值为此父节点。如果没有这种情况，则将回传值不断向父节点回传，保证最后得到的时最近公共祖先。

终止条件下好后，写本步操作，分辨获得节点的left和right的回传值，向下递归。

检查回传值是否两边都有，如果都有则更新回传值为父节点，如果只有一边，那么就更新为有值的一边。

思路二：哈希存父节点的值，然后转化成求p节点所在的链表和q节点所在的链表相交位置的问题。

解决方法： 1：递归

class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root: return if root is p or root is q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root if not left: return right if not right: return left

2：哈希+相交链表

class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': dic = {root:None} def dfs(node): if node: if node.left: dic[node.left] = node if node.right: dic[node.right] = node dfs(node.left) dfs(node.right) dfs(root) l1, l2 = p, q while(l1!=l2): l1 = dic.get(l1, q) l2 = dic.get(l2, p) return l1