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

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

原创 小猿同学 程序IT圈 文章源自JAVA秀-https://www.javaxiu.com/12227.html

收录于话题文章源自JAVA秀-https://www.javaxiu.com/12227.html

#Leecode刷题文章源自JAVA秀-https://www.javaxiu.com/12227.html

110个文章源自JAVA秀-https://www.javaxiu.com/12227.html

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！文章源自JAVA秀-https://www.javaxiu.com/12227.html

文章源自JAVA秀-https://www.javaxiu.com/12227.html

今天和大家聊的问题叫做 二叉树的最近公共祖先，我们先来看题面：文章源自JAVA秀-https://www.javaxiu.com/12227.html

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/文章源自JAVA秀-https://www.javaxiu.com/12227.html

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.文章源自JAVA秀-https://www.javaxiu.com/12227.html

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。文章源自JAVA秀-https://www.javaxiu.com/12227.html

文章源自JAVA秀-https://www.javaxiu.com/12227.html

示例

文章源自JAVA秀-https://www.javaxiu.com/12227.html

解题

文章源自JAVA秀-https://www.javaxiu.com/12227.html

非递归算法文章源自JAVA秀-https://www.javaxiu.com/12227.html

文章源自JAVA秀-https://www.javaxiu.com/12227.html

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 = parent_map
;        }// 同理遍历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;    }};

递归算法文章源自JAVA秀-https://www.javaxiu.com/12227.html

文章源自JAVA秀-https://www.javaxiu.com/12227.html

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;};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。文章源自JAVA秀-https://www.javaxiu.com/12227.html

上期推文：文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode1-220题汇总，希望对你有点帮助！文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战221：最大正方形文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战222：完全二叉树的节点个数文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战223：矩形面积文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战224：基本计算器文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战225：用队列实现栈文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战226：翻转二叉树文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战227：基本计算器 II文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战228：汇总区间文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战229：求众数 II文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战230：二叉搜索树中第K小的元素文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战231：2的幂文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战232：用栈实现队列文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战233：数字 1 的个数文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战234：回文链表文章源自JAVA秀-https://www.javaxiu.com/12227.html

LeetCode刷题实战235：二叉搜索树的最近公共祖先文章源自JAVA秀-https://www.javaxiu.com/12227.html

文章源自JAVA秀-https://www.javaxiu.com/12227.html