题解 | #在二叉树中找到两个节点的最近公共祖先#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    vector<int> find_path(TreeNode* root, int target) {
        queue<TreeNode*> q;
        unordered_map<TreeNode*, TreeNode*> parents;
        q.push(root);
        vector<int> path;
        while (!q.empty()) {
            TreeNode* current = q.front();
            q.pop();
            if (current->left) {
                q.push(current->left);
                parents[current->left] = current;
            }
            if (current->right) {
                q.push(current->right);
                parents[current->right] = current;
            }
            if (current->val == target) {
                TreeNode* node = current;
                while (node) {
                    path.push_back(node->val);
                    node = parents[node];
                }
                break;
            }
        }
        reverse(path.begin(), path.end());
        return path;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        int ans;
        vector<int> patho1 = find_path(root, o1);
        vector<int> patho2 = find_path(root, o2);
        int i = 0;
        int j = 0;
        while (i < patho1.size() && j < patho2.size()) {
            if (patho1[i] == patho2[j]) {
                ans = patho1[i];
            }
            i++;
            j++;
        }
        return ans;
    }
};

寻找二叉树里的任意两个节点的最近公共祖先节点。

思路总结：

1.先通过广度优先算法，输出各自从root节点到目标节点的路径。

2.循环对比两者的路径，返回最后一个相等的节点值

ps：寻找路径时，广度优先可以借助队列queue的先进先出原则，进行实现。

节点之间的父子关系可以借助无序的字典 unordered_map<> parents 实现父子之间的联系

等找到目标节点后，循环遍历取出此节点以及他的父亲节点的数值，放于路径当中。

此时为儿子到父亲的路径，仍然需要reverse(begin(), end()),将路径反转