今天和大家聊的问题叫做 二叉搜索树的最近公共祖先，我们先来看题面：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
示例
示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。
解题
这题让求二叉搜索树的最近公共祖先，而二叉搜索树的特点就是左子树的所有节点都小于当前节点，右子树的所有节点都大于当前节点，并且每棵子树都具有上述特点，所以这题就好办了，从更节点开始遍历
- 如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
- 如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
- 如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。
递归法
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) elif root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) else: return root
非递归：
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ while root: if root.val > max(p.val, q.val): root = root.left elif root.val < min(p.val, q.val): root = root.right else: return root return root
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
