写点什么

LeetCode 题解:236. 二叉树的最近公共祖先,存储父节点,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 01 月 12 日
LeetCode题解:236. 二叉树的最近公共祖先,存储父节点,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/


解题思路:


  1. 先遍历二叉树的所有节点,用 Map 保存每个子节点的父节点。

  2. 使用 Map,遍历 p 的所有父节点,将其保存在 Set 中。

  3. 遍历 q 的所有父节点,当父节点第一次存在于 Set 中时,其就是最近公共祖先。


/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } */// 保存每个节点的父节点let parentMap = new Map();
// 递归遍历所有节点,并保存其父节点function dfs(node) { if (node.left) { // 如果子节点存在,则将其父节点保存到Map中 parentMap.set(node.left, node); // 继续递归遍历子节点 dfs(node.left); } if (node.right) { parentMap.set(node.right, node); dfs(node.right); }}/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */var lowestCommonAncestor = function (root, p, q) { dfs(root); // 遍历二叉树的所有节点,保存其子父关系
// 用Set保存p的所有父节点 let visitedSet = new Set();
// 遍历并保存所有p的父节点 while (p) { // 每次遍历的p都是一个父节点,将其保存到Set中 visitedSet.add(p); // 不断在Map中查找p的父节点,并将其更新到p,用于下一次遍历 p = parentMap.get(p); }
// 遍历q的父节点,如果父节点已在visitedSet中保存过,则它就是最近公共祖先 while (q) { // 当第一次发现q在visitedSet中,那么它就是最近公共祖先,将其返回即可 if (visitedSet.has(q)) { return q; } // 每次遍历都查找q的父节点,并将其更新,继续循环 q = parentMap.get(q); }};
复制代码


发布于: 2021 年 01 月 12 日阅读数: 25
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:236. 二叉树的最近公共祖先,存储父节点,JavaScript,详细注释