865.求最深公共子树

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

方法一：
二次dfs

做一次深度搜索记录下每个点的深度

找深度其实要利用到父节点，不管是左还是右子树，通常都是父节点加1

用数学的函数遍历并且记录下深度最大的值，便于比较

第二次深度搜索是为了找到深度最大的子树的节点真正的求答案
'''
class Solution {
Map<TreeNode, Integer> depth;
int max_depth;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
depth = new HashMap();
depth.put(null, -1); //首层是1还是0不重要因为不是求深度
dfs(root, null);//这里两个null表示父节点
max_depth = -1;//初始化
for (Integer d: depth.values())
max_depth = Math.max(max_depth, d);
return answer(root);
}

public void dfs(TreeNode node, TreeNode parent) {
    if (node != null) {
        depth.put(node, depth.get(parent) + 1); 记录深度
        dfs(node.left, node)
        dfs(node.right, node);
    }
}

public TreeNode answer(TreeNode node) {//始终只是中间过程而已
    if (node == null || depth.get(node) == max_depth) //这个点为空 或者已经是最大深度了 答案
        return node;
    TreeNode L = answer(node.left), //如果左子树为空 方法体里返回的node也会为空的 找到则为左最深
             R = answer(node.right);//同上的 找到则为右最深
    if (L != null && R != null) return node; //从上面的条件可以看到 如果左右均不为空 那么说明左右都有最大深度了，那么这个点就是要找的点
    if (L != null) return L; //说明在左子树中 
    if (R != null) return R;
    return null; //左右子树都没  只要找不到最深的 都为 null
}

}

作者：LeetCode
链接：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/solution/ju-you-suo-you-zui-shen-jie-dian-de-zui-xiao-zi-sh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间空间复杂度都为o（N），即考虑最坏情况，都需要遍历N次，申请N个空间
这里有个小技巧，一般来说使用递归都会让时间空间复杂度变成o(N)，说得不对请轻喷

方法二：
一次dfs
主要利用自定义的类用于返回结果和存储
递归的思想还是需要好好磨炼，个人觉得递归就是一种基于整体已实现的思路

（1）如果左右子树的深度相等，那么就返回node节点
（2）如果左子树大于右子树，则返回左节点，否则返回右节点

public treenode dfs（Treenode node）{
 if（node==null） return new（null，0）；
TReenode L= dfs（）； 
}