【2024考研】题解26 | #二叉搜索树的最近公共祖先#

#include <vector>
class Solution {
public:
    /**
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
     vector<int> getPath(TreeNode *root, int target){
       vector<int> path;
       TreeNode *node = root;
       
       while (target != node->val) {
            path.push_back(node->val);
		 //二叉搜索树 左叶子 < 根 < 右叶子 
            if(target < node->val){
                node = node->left;
            }
            else {
                node = node->right;
            }
       }
       //把最后的叶子结点值也要输进去，循环中未涉及
       path.push_back(node->val);
       return path;
     }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        vector<int> path_p = getPath(root, p);
        vector<int> path_q = getPath(root, q);

        int res;

        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){
            if(path_p[i] == path_q[i]){
                res  = path_p[i];
            }
            else {
                break;
            }
        }
        return res;
    }
};

基本算法思路：

• 首先定义一个辅助函数getPath，该函数接受当前节点和目标值作为参数，返回从根节点到目标节点的路径。
• 初始化一个空的路径path，将当前节点赋值给node。
• 循环条件是目标值不等于当前节点的值： 将当前节点的值加入到路径path中。由于是二叉搜索树，如果目标值小于当前节点的值，说明目标节点在当前节点的左子树中，将当前节点的左子节点赋值给node。如果目标值大于当前节点的值，说明目标节点在当前节点的右子树中，将当前节点的右子节点赋值给node。
• 循环结束后，将当前节点的值加入到路径path中，表示找到了目标节点。
• 返回路径path。

• 在函数lowestCommonAncestor中，分别调用辅助函数getPath获取节点p和节点q的路径。
• 初始化一个变量res，用来存储最近公共祖先的值。
• 遍历路径path_p和path_q，比较对应位置的节点值，如果相等，则更新res为当前节点值。
• 如果不相等，则跳出循环。
• 返回res，即为最近公共祖先的值。

时间复杂度：

O(n)，其中n是二叉搜索树的节点个数。需要遍历树的路径，最坏情况下，需要遍历整个树。

空间复杂度：

O(n)，需要存储从根节点到目标节点的路径，最坏情况下，路径的长度为n，因此空间复杂度是O(n)。