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

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

    // 二叉搜索树，左节点 < 根节点 < 右节点
    // 疑惑1，为啥不使用遍历一遍再找位置
    // 树的遍历方式只是一个全体方式，若抠出部分树，遍历结果也是不一样的。文字难以表达
    // 疑惑2，若不是二叉搜索树，有没有更好的遍历方式？ 
    void find_path(TreeNode* root, int tar, vector<int>& v)
    {
        while (root->val != tar) {
            v.push_back(root->val);
            // std::cout << root->val << " ";
            if(root->val > tar) root = root->left;      // 在二叉搜索树中，表示小于则表示节点在左侧
            // if(root->val <= tar) root = root->right;  // 该写法会导致bug出现~
            else root = root->right;
        }
        v.push_back(root->val);     // 找到了，需要放到容器里面
    }

    void find_path(TreeNode* root, int target, vector<int>&v, int& id)  // 前序遍历方式找路径，解答疑惑1：如何通过遍历方式拿到合适的访问顺序
    {
        if(!root) return;
        v.push_back(root->val);
        if(root->val == target)
        {
            id = v.size();
            return;
        }
        find_path(root->left, target, v, id);
        find_path(root->right, target, v, id);
        if(id != -1) return;
        v.pop_back();
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // // write code here
        // 遍历方式 1
        // vector<int> p_v;
        // vector<int> q_v;
        // find_path(root, p, p_v);
        // find_path(root, q, q_v);

        // int res = -1;
        // // 对两个数组进行同步遍历，找到最近的公共节点
        // int num = min(p_v.size(), q_v.size());

        // for(int i = 0; i < num; ++i)
        // {
        //     if(p_v[i] == q_v[i]) res = p_v[i];
        // } 
        // return res;

        // // 递归方式
        // if (!root) return -1;
        // // 在当前节点的两侧
        // if((p >= root->val && q <= root->val) || (p <=root->val && q >=root->val)) return root->val;
        // // 遍历左侧,pq均在节点的左侧
        // else if(p < root->val && q < root->val) return lowestCommonAncestor(root->left, p, q);
        // // pq均在节点的右侧 
        // else return lowestCommonAncestor(root->right, p, q);    

        // 遍历方式2,该方式不局限与二叉搜索树
        vector<int> p_v;
        vector<int> q_v;
        int id1 = -1, id2 = -1;
        find_path(root, p, p_v, id1);
        find_path(root, q, q_v, id2);

        int res = -1;
        // 对两个数组进行同步遍历，找到最近的公共节点
        int num = min(p_v.size(), q_v.size());

        for(int i = 0; i < num; ++i)
        {
            if(p_v[i] == q_v[i]) res = p_v[i];
        } 
        return res;      
    }
};