文章目录加载中
【LeetCode 236.二叉树的最近公共祖先】双解法:递归实现 + 利用父指针
题目描述:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
# 解法 1: 递归实现(推荐)
这题相较于 LeetCode 235.二叉搜索树的最近公共祖先 的递归思考起来比较有难度。
封装一个 recurseTree 递归函数,它返回 true/false,代表当前二叉树中是否存在 p、或者存在 q、或者两个节点都存在。在 recurseTree 递归过程中,如果发现当前二叉树同时存在 p 和 q,那么就更新最近公共祖先。
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 原文地址:https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-binary-tree/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
let res = root;
recurseTree(root);
return res;
/**
* @return {Boolean} 以node为根的二叉树中是否有p或者q
*/
function recurseTree(node) {
if (!node) return false;
const left = recurseTree(node.left, p, q) ? 1 : 0;
const right = recurseTree(node.right, p, q) ? 1 : 0;
const mid = p === node || q === node ? 1 : 0;
// 如果p和q都出现在以node为根的二叉树中
if (left + right + mid >= 2) {
res = node;
}
return left + right + mid > 0;
}
};
# 解法 2: 利用父指针
父指针的关系可以保存在一个哈希表中:<node, node'parent>
。那么对 node 来说,它的所有祖先节点就是从 node 开始,一直向上遍历父亲节点,统计过程中所有经历的节点,这些节点组成的集合就是所有祖先节点。
整体思路如下:
- 遍历二叉树,直到 p 和 q 都被遍历完
- 统计 p 的所有祖先节点,放入集合 set 中
- 从 q 开始,不断向上访问祖先节点,每次都检查节点是否在集合 set 中
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 原文地址:https://xxoo521.com/2020-04-18-lowest-common-ancestor-of-binary-tree/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
const queue = [root];
const map = new Map();
map.set(root, null);
while (!map.has(p) || !map.has(q)) {
const first = queue.shift();
if (first.left) {
map.set(first.left, first);
queue.push(first.left);
}
if (first.right) {
map.set(first.right, first);
queue.push(first.right);
}
}
const ancestors = new Set();
while (p) {
ancestors.add(p);
p = map.get(p);
}
while (!ancestors.has(q)) {
q = map.get(q);
}
return q;
};
# 更多资料
整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇
- 📖Blog:剑指 Offer 题解 + JS 代码
- 🐱Github :https://github.com/dongyuanxin/blog
- 🌟 公众号:心谭博客
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog