力扣 hot100: 二叉树公共祖先

二叉树公共祖先

题目链接: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=problem-list-v2&envId=2cktkvj

题目描述

样例输入

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

解题思路

这个题主要是通过遍历树, 然后来构造一颗树, 指向父亲节点, 然后就可以转换为链表交叉的问题

然后有些边界条件要注意下

ac 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    const int inf = 1e9+7;
    map<int, bool> m1, m2;
    map<int, int> tree; // val , father
    map<int, TreeNode*> record_v_n;
    map<TreeNode*, int> record_n_v;

    void visit(TreeNode* p) {
        if (p == NULL)
            return;
        record_v_n[p->val] = p; // 记录每个 val 对应的节点
        record_n_v[p] = p->val;
        visit(p->left);
        if (p->left != NULL)
            tree[p->left->val] = p->val;
        visit(p->right);
        if (p->right != NULL)
            tree[p->right->val] = p->val;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        tree[inf] = inf ;
        tree[root -> val] = inf;
        visit(root);
        int v1 = record_n_v[p];
        int v2 = record_n_v[q]; 
        for( ;  ;)
        {
            m1[v1] = 1;  m2[v2] = 1;
            if(m2[v1]) return record_v_n[v1];
            if(m1[v2]) return record_v_n[v2];
            v1 = tree[v1] ; v2 = tree[v2];
            if(v1 == inf && v2 == inf) break;
        }
        return root ; 
    }
};