前言
最近的工作实在太忙，没有充足的时间静下心来总结一些系列的知识，所以这段时间就先碎片化的做些算法题，找找手感。
题目
https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/
给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
一个节点的 子树 是该节点加上它的所有后代的集合。
返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
题目拆解
其实这道题题目描述的不太好，看了好久我才明白这题是啥意思。
其实本质上，这道题就是要做两件事，
-
第一件事，找到所有最深的节点，因为存在并列深度的情况，所以是找到所有最深的节点。
-
找到一个能把所有最深节点都包含到自己子树里的最小的树。
呐，就是这么两件事。
所以题目拆解完了，该怎么做也就知道了。
-
找到所有的最深节点：深度优先，给每一个节点和他的深度维护一个映射关系，最后排序得到一个最深的深度值。
-
找到一个把所有最深的节点都包含的子树（详细说下这个）。
找到一个把所有最深的节点都包含的子树
这个判断起来其实也不复杂，大体来说分为两步，还是深度优先。
-
看看最大深度是不是在自己子树里？左子树里还是右子树里？还是都没有？
-
然后判断是返回自己？还是返回子树？还是返回null？
然后再来解释这个怎么判断返回自己还是返回子树，三种情况
-
如果最深节点不在自己这，返回null；
-
如果最深节点左右子树都有，那就返回自己。
-
最深节点在左子树里，返回左子树，在右子树里，返回右子树。
好了要做的事情就这些。可以写代码了
class Solution {
private Map<TreeNode, Integer> node2Deep = new HashMap<>();
private int maxDeep;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
node2Deep = new HashMap<>();
maxDeep = -1;
node2Deep.put(null, -1);
// 第一次深度优先,找到标记所有节点的深度
dfsFirst(root, null);
// 遍历找到最深的深度
for (Integer value : node2Deep.values()) {
maxDeep = Math.max(value, maxDeep);
}
// 第二次深度优先,找到需要返回的子树
return dfsSecond(root);
}
void dfsFirst(TreeNode self, TreeNode parent) {
if (self == null) return;
node2Deep.put(self, node2Deep.get(parent) + 1);
dfsFirst(self.left, self);
dfsFirst(self.right, self);
}
TreeNode dfsSecond(TreeNode self) {
// 走到头了,返回null
if (self == null) return self;
// 遇到最深节点了,返回自己.
if (node2Deep.get(self) == maxDeep) return self;
// 往下看看左右子树里面有没有最深节点
// 注意这里只要返回不是null,就说明包含最深节点
TreeNode left = dfsSecond(self.left);
TreeNode right = dfsSecond(self.right);
// 第一种情况,说明左右子树都包含最深节点,返回自己
if (left != null && right != null) return self;
// 第二种情况,左右哪边有最深节点,返回哪边
if (left != null) return left;
if (right != null) return right;
// 第三种情况,最深节点不在自己家,返回null
return null;
}
}
总结
刷leecode时，要认真理解题意，比如这道题，就是把题目和示例看了好几遍，才明白到底要干一个什么事。
