1. 题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
235. 二叉搜索树的最近公共祖先 - 图1
示例 1:

  1. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
  2. 输出: 6 
  3. 解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

  1. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
  2. 输出: 2
  3. 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

    2. 解题思路

    对于这道题目，我们可以使用递归或者迭代来实现。

1）递归实现：对于二叉树搜索树：

  • 如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树；
  • 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树；
  • 如果 p.val 和 q.val 一个比 root.val 大，一个比 root.val 小，那说明这两个节点的最进公共祖先就是root；

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况选，我们需要深度优先遍历整棵二叉树；
  • 空间复杂度：O(n)，我们需要递归遍历这棵树，所以空间复杂度为O(n)；

2）迭代实现：我们可以使用一个 while 循环，当 root 为 null 时就结束循环：

  • 如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树，root=root.left，遍历到 root 的左子节点。
  • 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树，root=root.right，遍历到 root 的右子节点。
  • 其他情况，当前的 root 就是最近公共祖先，结束遍历，直接结束循环。

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况下，我们需要深度优先遍历整棵二叉树；
  • 空间复杂度：O(1)，我们只需要常量空间来操作。

    3. 代码实现

    递归实现： ```javascript /**
    • Definition for a binary tree node.
    • function TreeNode(val) {
    • this.val = val;
    • this.left = this.right = null;
    • } */

/**

  • @param {TreeNode} root
  • @param {TreeNode} p
  • @param {TreeNode} q
  • @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { if(p.val < root.val && q.val < root.val){
    1.  return lowestCommonAncestor(root.left, p, q)
    } if(p.val > root.val && q.val > root.val){
     return lowestCommonAncestor(root.right, p, q)
    } return root }; **迭代实现：**javascript /**
  • Definition for a binary tree node.
  • function TreeNode(val) {
  • this.val = val;
  • this.left = this.right = null;
  • } */

/**

  • @param {TreeNode} root
  • @param {TreeNode} p
  • @param {TreeNode} q
  • @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { while(root){
     if(p.val < root.val && q.val < root.val){
     root = root.left
 }else if(p.val > root.val && q.val > root.val){
     root = root.right
 }else{
     break
 }
    } return root }; ```

    4. 提交结果

    递归实现：
    image.png
    迭代实现：
    image.png