在二叉树中找到两个节点最近公共祖先
给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
输入:[3,5,1,6,2,#,8,#,#,7,4],2,8
返回值:3
分析：二叉树的常规解法是递归，这次我们不用递归来做。采用备忘录的模型，我们可以依次记录每个节点对应的父节点是谁，比如memo[6]=5，这表明6的父节点是5，使用递归的方式依次完成记录。然后根据记录的结果进行求解。具体代码如下：
def commonAncestor(root,p,q):memo={}def dfs(root): #使用递归算法，完成备忘录记录memo[root.left] = rootmemo[root.right] = rootdfs(root.left)dfs(root.right)dfs(root)l1,l2 = p,qwhile l1 != l2:l1 = memo.get(l1) if memo.get(l1) is not None else ql1 = memo.get(l2) if memo.get(l2) is not None else preturn l1
欢迎关注哦！！！
二斌养鸡场