【Leetcode刷题篇】leetcode236 二叉树的最近公共祖先
发布日期:2021-06-29 15:33:26
浏览次数:2
分类:技术文章
本文共 1066 字,大约阅读时间需要 3 分钟。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
题解:先对这棵树遍历,遍历找到每个数的父节点。之后对第一个结点进行访问,并将其父节点存储。对第二个结点访问,如果其出现在存储中,返回,否则继续找其父亲。
package com.lcz.leetcode;/** * 二叉树的最近公共祖先 */import java.util.*;public class Leetcode236 { class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val = x; } } // 哈希表存储父节点 HashMapparent = new HashMap<>(); // 存储是否访问过 HashSet visited = new HashSet<>(); public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 对其遍历 dfs(root); while(p!=null) { visited.add(p.val); p = parent.get(p.val); } while(q!=null) { if(visited.contains(q.val)) { return q; } q = parent.get(q.val); } return null; } private void dfs(TreeNode root) { if(root.left!=null) { parent.put(root.val,root); dfs(root.left); } if(root.right!=null) { parent.put(root.val,root); dfs(root.right); } }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109493435 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月23日 18时49分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
分治法:241. 为运算表达式设计优先级
2019-04-29
广度优先遍历:二进制矩阵中的最短路径
2019-04-29
广度优先遍历:set集合的速度远远比list快:完全平方数
2019-04-29
广度+深度:岛屿的最大面积/岛屿数量
2019-04-29
torch 模型运行时间与forward没对应的可能原因
2019-04-29
130. 被围绕的区域
2019-04-29
欧式距离、余弦相似度和余弦距离
2019-04-29
transform 等效转换(参考源码)
2019-04-29
Docker学习(二):Docker基本操作(控制容器)
2019-04-29
Unity之C#学习笔记(0):环境配置与上手 HelloWorld
2019-04-29
高并发高可用秒杀系统(一)
2019-04-29
php如何将base64数据流文件转换为图片文件?
2019-04-29
JavaScript 的addEventListener() 事件监听详解!
2019-04-29
JavaScript的DOMContentLoaded事件和load的区别?
2019-04-29
PHP+JavaScript实现图片预览上传功能开发!
2019-04-29
JSONView - Chrome插件安装详解!(谷歌浏览器插件)!
2019-04-29
上传图片到阿里云OSS和获取上传图片的url的详解 !
2019-04-29
webstorm 和 phpstorm 有什么区别呢?做 WEB 开发用哪个好?
2019-04-29
常见位运算
2019-04-29
武大学生用python敲出樱花开放 | 附源码
2019-04-29