​LeetCode刷题实战236:二叉树的最近公共祖先

程序IT圈

共 5356字,需浏览 11分钟

 ·

2021-04-14 14:03

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 二叉树的最近公共祖先,我们先来看题面:
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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

示例


解题


非递归算法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode *> stack;
        stack.push(root);
        map<TreeNode *, TreeNode *> parent_map;
        parent_map[root] = NULL;
        while(parent_map.find(p) == parent_map.end() || parent_map.find(q) == parent_map.end()){
            TreeNode *node = stack.top();
            stack.pop();
            if(node -> left != NULL){
                parent_map[node -> left] = node;
                stack.push(node -> left);
            }
            if(node -> right != NULL){
                parent_map[node -> right] = node;
                stack.push(node -> right);
            }
        }
        set<TreeNode *> p_parent;
        p_parent.insert(p);
// 迭代父节点map,这里的循环逻辑为,父节点字典中如果一直能够找到p节点的父节点,就进入循环
// 这样可以一直得到p节点的父节点列表。
        while(parent_map.find(p) != parent_map.end()){
            p_parent.insert(parent_map[p]);
            p = parent_map[p];
        }
// 同理遍历q节点的父节点列表,因为是逆序遍历,所以当它存在于p节点的列表时,找到的就是p和q的最近公共祖先
        while(parent_map.find(q) != parent_map.end()){
            if(p_parent.find(q) != p_parent.end()){
                return q;
            }
            q = parent_map[q];
        }
        return root;
    }
};

递归算法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int num = contain_node(root, p, q);
        return ans;
    }
    int contain_node(TreeNode* root, TreeNode* p, TreeNode* q){
        if(!root) return 0;
        int mid = 0;
        if(root == p || root == q) mid = 1;
        int left = contain_node(root -> left, p, q);
        if(mid + left == 2){
            if(!ans) ans = root;
            return 2;
        }
        int right = contain_node(root -> right, p, q);
        if(left + right + mid >= 2){
            if(!ans) ans = root;
            return 2;
        }
        return left + mid + right;
    }
private:
    TreeNode* ans = NULL;
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-220题汇总,希望对你有点帮助!

LeetCode刷题实战221:最大正方形

LeetCode刷题实战222:完全二叉树的节点个数

LeetCode刷题实战223:矩形面积

LeetCode刷题实战224:基本计算器

LeetCode刷题实战225:用队列实现栈

LeetCode刷题实战226:翻转二叉树

LeetCode刷题实战227:基本计算器 II

LeetCode刷题实战228:汇总区间

LeetCode刷题实战229:求众数 II

LeetCode刷题实战230:二叉搜索树中第K小的元素

LeetCode刷题实战231:2的幂

LeetCode刷题实战232:用栈实现队列

LeetCode刷题实战233:数字 1 的个数

LeetCode刷题实战234:回文链表

LeetCode刷题实战235:二叉搜索树的最近公共祖先


浏览 40
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报