题目
https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
题解
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);
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);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)