当前位置:网站首页>leetcode 865. Smallest Subtree with all the Deepest Nodes | 865.具有所有最深节点的最小子树(树的BFS,parent反向索引map)
leetcode 865. Smallest Subtree with all the Deepest Nodes | 865.具有所有最深节点的最小子树(树的BFS,parent反向索引map)
2022-07-08 00:37:00 【寒泉Hq】
题目
https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
题解
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
// 层序遍历,记录最深层
Queue<TreeNode> preQueue = new LinkedList<>();
Queue<TreeNode> curQueue = new LinkedList<>();
Queue<TreeNode> nextQueue;
curQueue.offer(root);
while (!curQueue.isEmpty()) {
preQueue = new LinkedList<>(curQueue);
nextQueue = new LinkedList<>();
while (!curQueue.isEmpty()) {
TreeNode cur = curQueue.poll();
if (cur.left != null) {
nextQueue.offer(cur.left);
}
if (cur.right != null) {
nextQueue.offer(cur.right);
}
}
if (nextQueue.isEmpty()) {
break;
}
curQueue = nextQueue;
}
// 建立树反向索引表
HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
dfs(root, parentMap);
// 从最深层每个节点向上找parent,路过时,节点经过次数count++,找到最早出现count==n的祖先
HashMap<Integer, Integer> countMap = new HashMap<>();
int n = preQueue.size();
while (!preQueue.isEmpty()) {
TreeNode cur = preQueue.poll();
while (cur != null) {
int count = countMap.getOrDefault(cur.val, 0) + 1;
if (count == n) {
return cur;
}
countMap.put(cur.val, count);
cur = parentMap.get(cur);
}
}
return null;
}
public void dfs(TreeNode node, HashMap<TreeNode, TreeNode> map) {
if (node.left != null) {
map.put(node.left, node);
dfs(node.left, map);
}
if (node.right != null) {
map.put(node.right, node);
dfs(node.right, map);
}
}
}
边栏推荐
- PHP to get information such as audio duration
- Apache multiple component vulnerability disclosure (cve-2022-32533/cve-2022-33980/cve-2021-37839)
- 2022国内十大工业级三维视觉引导企业一览
- A comprehensive and detailed explanation of static routing configuration, a quick start guide to static routing
- DataWorks值班表
- 什么样的MES系统才是好系统
- Clickhouse principle analysis and application practice "reading notes (8)
- 图解网络:揭开TCP四次挥手背后的原理,结合男女朋友分手的例子,通俗易懂
- Voice of users | winter goes and spring comes, waiting for flowers to bloom -- on gbase 8A learning comprehension
- Beaucoup d'enfants ne savent pas grand - chose sur le principe sous - jacent du cadre orm, non, ice River vous emmène 10 minutes à la main "un cadre orm minimaliste" (collectionnez - le maintenant)
猜你喜欢
关于TXE和TC标志位的小知识
快速熟知XML解析
metasploit
How to make enterprise recruitment QR code?
云原生应用开发之 gRPC 入门
leetcode 873. Length of Longest Fibonacci Subsequence | 873. 最长的斐波那契子序列的长度
图解网络:揭开TCP四次挥手背后的原理,结合男女朋友分手的例子,通俗易懂
List of top ten domestic industrial 3D visual guidance enterprises in 2022
QT -- create QT program
burpsuite
随机推荐
Is it necessary for project managers to take NPDP? I'll tell you the answer
If time is a river
Keras' deep learning practice -- gender classification based on inception V3
Graphic network: uncover the principle behind TCP's four waves, combined with the example of boyfriend and girlfriend breaking up, which is easy to understand
数据链路层及网络层协议要点
pb9.0 insert ole control 错误的修复工具
Voice of users | winter goes and spring comes, waiting for flowers to bloom -- on gbase 8A learning comprehension
Version 2.0 of tapdata, the open source live data platform, has been released
Codeforces Round #649 (Div. 2)——A. XXXXX
微信小程序uniapp页面无法跳转:“navigateTo:fail can not navigateTo a tabbar page“
From starfish OS' continued deflationary consumption of SFO, the value of SFO in the long run
cv2读取视频-并保存图像或视频
How to make enterprise recruitment QR code?
给刚入门或者准备转行网络工程师的朋友一些建议
PHP calculates personal income tax
如何制作企业招聘二维码?
leetcode 866. Prime Palindrome | 866. 回文素数
powerbuilder 中使用线程的方法
Introduction to ADB tools
Remote Sensing投稿經驗分享