leetcode编程算法随笔 -865. 具有所有最深节点的最小子树

https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/description/

记录这个的目的：

1. 对于递归算法，在过程中它可以"承载"许多信息，有局部的有全局的，适当组合可以降低复杂度。另外需要注意，递归中的顺序。

2. 加大学的比例，降低练习比例。扩展一些看似已知已掌握知识的。

思路1

先dfs或bfs 求出最大深度

然后再找所有深度为最大深度的节点的最近公共祖先

这基本是最笨的方法

思路2

主要参考灵茶山艾府

考虑子树，相对于考虑只节点，多了一些概括与抽象

若一个节点是目标节点，那么它的左右子树深度都是有最大深度的，但在遍历过程中，最大高度不能立即获得，因此需要用全局变量维护。

# 这里注意一个问题，许多时候，当有多个思路看起来可行的时候。很容易在一个看似不可行的点把思路"剪枝"掉。

考虑，这个方法是不是会遗漏一些情况

首先，若一个节点的左右子树的高度不一样，那么它一定不是目标节点。

其次，若一个节点的左右子树高度一样，并且这个高度比原当前的高，那么更新

特殊情况,当一个节点没有子节点，且是最深的节点的时候，它是目标节点

思路3

主要参考leetcode官方

与2相似，但不再维护最大深度的全局变量，虽然不维护全局变量，但是这信息需要以返回数值的形式存着

否则可能会犯错：在递归过程中，后面出现的左右子树高度相等的节点，其高度并没有原来的高

具体的实现