剑指68：二叉搜索树的最近公共祖先

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // 求根节点到两个指定节点的路径
        vector<int> path_p = getPath(root, p);
        vector<int> path_q = getPath(root, q);

        int res = 0;
        // 比较两条路径，找到第一个不同的点
        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;
    }

    // 求根节点到目标节点的路径
    vector<int> getPath(TreeNode* root, int target) {
        vector<int> path;
        TreeNode* node = root;
        // 所有节点的值都是唯一的，比较值即可
        while (node->val != target) {
            path.push_back(node->val);
            if (target < node->val) node = node->left; // 值小的在左子树
            else node = node->right; // 值大的在右子树
        }
        path.push_back(node->val);
        return path;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return find(root, p->val, q->val);
    }

    // 二叉树中找到 val1 和 val2 的最近公共祖先
    TreeNode* find(TreeNode* root, int val1, int val2) {
        if (!root) return nullptr;

        // 前序位置
        // 若遇到目标值，则直接返回
        if (root->val == val1 || root->val == val2) {
            return root;
        }

        TreeNode* left = find(root->left, val1, val2);
        TreeNode* right = find(root->right, val1, val2);
        // 后序位置
        // 若左右节点都不空，则当前节点是 LCA
        if (left && right) {
            return root;
        }
        return left ? left : right;
    }
};