当前位置:网站首页>leetcode 865. Smallest Subtree with all the Deepest Nodes | 865. The smallest subtree with all the deepest nodes (BFs of the tree, parent reverse index map)
leetcode 865. Smallest Subtree with all the Deepest Nodes | 865. The smallest subtree with all the deepest nodes (BFs of the tree, parent reverse index map)
2022-07-08 02:03:00 【Cold spring HQ】
subject
https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
Answer key
/** * 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) {
// Sequence traversal , Record the deepest layer
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;
}
// Create a tree reverse index table
HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
dfs(root, parentMap);
// Look up from every node in the deepest layer parent, Passing by , Node passing times count++, Find the earliest count==n The ancestors of the
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);
}
}
}
边栏推荐
- 云原生应用开发之 gRPC 入门
- Flutter 3.0框架下的小程序运行
- 电路如图,R1=2kΩ,R2=2kΩ,R3=4kΩ,Rf=4kΩ。求输出与输入关系表达式。
- C language -cmake cmakelists Txt tutorial
- Ml self realization / linear regression / multivariable
- From starfish OS' continued deflationary consumption of SFO, the value of SFO in the long run
- Vim 字符串替换
- 2022国内十大工业级三维视觉引导企业一览
- 阿锅鱼的大度
- body有8px的神秘边距
猜你喜欢
A comprehensive and detailed explanation of static routing configuration, a quick start guide to static routing
Why does the updated DNS record not take effect?
Ml backward propagation
Neural network and deep learning-5-perceptron-pytorch
I don't know. The real interest rate of Huabai installment is so high
关于TXE和TC标志位的小知识
leetcode 873. Length of Longest Fibonacci Subsequence | 873. 最长的斐波那契子序列的长度
Alo who likes TestMan
From starfish OS' continued deflationary consumption of SFO, the value of SFO in the long run
C语言-模块化-Clion(静态库,动态库)使用
随机推荐
MySQL查询为什么没走索引?这篇文章带你全面解析
直接加比较合适
OpenGL/WebGL着色器开发入门指南
PHP calculates personal income tax
Remote Sensing投稿經驗分享
Redisson分布式锁解锁异常
Analysis ideas after discovering that the on duty equipment is attacked
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
SQLite3 data storage location created by Android
Le chemin du poisson et des crevettes
COMSOL --- construction of micro resistance beam model --- final temperature distribution and deformation --- addition of materials
PHP 计算个人所得税
[error] error loading H5 weight attributeerror: 'STR' object has no attribute 'decode‘
JVM memory and garbage collection-3-direct memory
Redisson distributed lock unlocking exception
[target tracking] |dimp: learning discriminative model prediction for tracking
Ml self realization /knn/ classification / weightlessness
数据链路层及网络层协议要点
Sword finger offer II 041 Average value of sliding window
Why does the updated DNS record not take effect?