思路：

1.当当前root==p or root == q 就将root返回，当同一层递归逻辑里的left 和 right都不为空时，说明当前root为所求lowest common ancestor；

2.若只有left空或只有right空，则返回非空的。因为非空的即为所求，是从底层一直回溯上来的；

3.若left和right都为空，则返回空。可能为叶子几点或该树的分叉不满足条件；

递归法：

# 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':#递归终止条件if root == p or root == q or root == None:return rootleft = self.lowestCommonAncestor(root.left, p, q)        #左right = self.lowestCommonAncestor(root.right, p, q)        #右#判断是否为lowest common ancestor逻辑if left != None and right != None:                     return rootelif left != None and right == None:return leftelif left == None and right != None:return rightelse:return None#更优雅的写法(判断是否为lowest common ancestor逻辑)：# if left and right:#     return root# if left:#     return left# return right

总结：

这道题目刷过的同学未必真正了解这里面回溯的过程，以及结果是如何一层一层传上去的。

那么我给大家归纳如下三点：

1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。

2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。

本题没有给出迭代法，因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。

References

leetcode-master/0236.二叉树的最近公共祖先.md at master · youngyangyang04/leetcode-master · GitHub