题解 | 二叉搜索树的最近公共祖先

1、解题思路

1. BST的性质：左子树的所有节点值小于当前节点值。右子树的所有节点值大于当前节点值。
2. LCA的性质：如果 p 和 q 分别位于当前节点的左右子树中，则当前节点就是它们的LCA。如果 p 或 q 等于当前节点，则当前节点就是它们的LCA。如果 p 和 q 都小于当前节点值，则LCA在左子树中。如果 p 和 q 都大于当前节点值，则LCA在右子树中。
3. 递归方法：根据BST的性质递归搜索LCA。
4. 迭代方法：使用循环代替递归，降低空间复杂度。

2、代码实现

C++（递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if (root == nullptr) {
            return -1;
        }

        if (p < root->val && q < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (p > root->val && q > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
            return root->val;
        }
    }
};

C++（迭代）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        while (root != nullptr) {
            if (p < root->val && q < root->val) {
                root = root->left;
            } else if (p > root->val && q > root->val) {
                root = root->right;
            } else {
                return root->val;
            }
        }
        return -1;
    }
};

Java（递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if (root == null) return -1;

        if (p < root.val && q < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (p > root.val && q > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root.val;
        }
    }
}

Java（迭代）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        while (root != null) {
            if (p < root.val && q < root.val) {
                root = root.left;
            } else if (p > root.val && q > root.val) {
                root = root.right;
            } else {
                return root.val;
            }
        }
        return -1;
    }
}

Python（递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        if not root:
            return -1
        
        if p < root.val and q < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p > root.val and q > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root.val

Python（迭代）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        while root:
            if p < root.val and q < root.val:
                root = root.left
            elif p > root.val and q > root.val:
                root = root.right
            else:
                return root.val
        return -1

3、复杂度分析

• 时间复杂度：O(h)，其中 h 是树的高度。最坏情况下为 O(n)（树退化为链表）。
• 空间复杂度：递归方法为 O(h)，迭代方法为 O(1)。