剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

在二叉搜索树中：

1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。

2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。

3.任意结点的左、右子树也分别为二叉搜索树.

即任意节点，左<根<右

 祖先的定义： 若节点 p 在节点 node 的左（右）子树中，或 p=node，则称 node是 p 的祖先。

最近公共祖先的定义： 设节点 node为节点 p,q的某公共祖先，若其左子节点node.left 和右子节点 node.right 都不是 p,q的公共祖先，则称node是 “最近的公共祖先” 。

根据以上定义，若node 是 p,q的 最近公共祖先 ，则只可能为以下情况之一：

1. p 和 q 在node 的子树中，且分列node的 异侧（即分别在左、右子树中）；
2. p =node，且 q在node的左或右子树中；
3. q =node，且 p在 node的左或右子树中；

本题给定了两个重要条件：① 树为 二叉搜索树 ，② 树的所有节点的值都是 唯一 的。根据以上条件，可方便地判断 p,q与 node 的子树关系，即：

若 node .val < p.val ，则 pp 在 node 右子树 中；
若 node .val > p.val ，则 pp 在node 左子树 中；
若 node .val = p.val ，则 p 和node 指向 同一节点 。

所以从根节点开始看，p,q都在node左子树中就去迭代（或搜索）node左子树，

p,q都在node右子树中就去迭代（或搜索）node右子树，

否则就返回node

方法一：迭代
循环搜索： 当节点node 为空时跳出；
当 p, q都在node 的 右子树 中，则遍历至 node.right ；
否则，当 p, q都在 node的 左子树 中，则遍历至 node.left ；
否则，说明找到了 最近公共祖先 ，跳出。
返回值： 最近公共祖先node。

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        while root:
            if root.val>p.val and root.val>q.val:
                root=root.left
            elif root.val<p.val and root.val<q.val:
                root=root.right
            else:
                break
        return root

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        while root:
            if root.val>p.val and root.val>q.val:
                root=root.left
            elif root.val<p.val and root.val<q.val:
                root=root.right
            else: return root

方法二：递归
递推工作：
当 p, q 都在node 的 右子树 中，则开启递归 node.right 并返回；
否则，当 p, q都在 noed 的 左子树 中，则开启递归 noed.left 并返回；

终止条件：就是都不满足返回节点node
返回值： 最近公共祖先node。

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        def dfs(root,p,q):
            if root.val > p.val and root.val > q.val:
                 return dfs(root.left,p,q)
            if root.val < p.val and root.val < q.val:
                return dfs(root.right,p,q)
            return root
        return dfs(root,p,q)
class Solution:
    def lowestCommonAncestor(self, root, p, q):
            if root.val > p.val and root.val > q.val:
                 return self.lowestCommonAncestor(root.left,p,q)
            if root.val < p.val and root.val < q.val:
                returnself.lowestCommonAncestor(root.right,p,q)
            return root