题意

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

解题思路

1. 后序遍历法，将pq的公共父节点问题转化为找到一个节点node使得p、q分别位于node的左右子树中；

   • 若p和q要么分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可。

   • 若p和q同时位于左子树，这里有两种情况，一种情况是left会返回p和q中较高的那个位置，而right会返回空，所以我们最终返回非空的left即可。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。

   • 若p和q同时位于右子树，同样这里有两种情况，一种情况是right会返回p和q中较高的那个位置，而left会返回空，所以我们最终返回非空的right即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回。

   1. 只要找到其中的一个结点，就不会继续往下找，比如同在左子树上，也就是上面说到的第二点；

   2. 如果是分别在两边子树上，那么left和right就都能够找到，此时返回的就是他们的父亲结点，也就是上面说到的第一点；

2. 找出两个结点的路径，对路径中的值进行比对，直到出现不一样的结点为止；

实现

# Definition for a binary tree node. # class TreeNode(object): #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None ​ class Solution(object):     def lowestCommonAncestor(self, root, p, q):         """         递归         :type root: TreeNode         :type p: TreeNode         :type q: TreeNode         :rtype: TreeNode         """         if not root or root == p or root == q:             return root                  left = self.lowestCommonAncestor(root.left, p, q)         right = self.lowestCommonAncestor(root.right, p, q)                  if not left:             return right         elif not right:             return left         return root ​   def lowestCommonAncestor(self, root, p, q):         """         比对路径         :type root: TreeNode         :type p: TreeNode         :type q: TreeNode         :rtype: TreeNode         """         pathP, pathQ = self.findPath(root, p), self.findPath(root, q)         lenP, lenQ = len(pathP), len(pathQ)         ans, x = None, 0         # 找出出现不一致的结点，则上一个结点则为最近公共结点         while x < min(lenP, lenQ) and pathP[x] == pathQ[x]:             ans, x = pathP[x], x + 1         return ans              def findPath(self, root, target):        """        获取结点的路径        """         stack = []         lastVisit = None         while stack or root:             if root:                 stack.append(root)                 root = root.left             else:                 peek = stack[-1]                 if peek.right and lastVisit != peek.right:                     root = peek.right                 else:                     if peek == target:                         return stack                     lastVisit = stack.pop()                     root = None         return stack