865. 具有所有最深节点的最小子树

用时:60min

被题目的深度误导,认为计算深度需要由上至下。实际上可以由下至上。

如果左右子树高度相同,返回节点本身以及深度

如果左子树比较深,说明最小最深在左子树,返回左子树以及自己的深度

如果右子树比较深,说明最小深度在右边,返回右子树以及自身深度

1
2
3
4
5
6
7
8
9
10
11
12
var subtreeWithAllDeepest = function(root) {
var dfs = function (root) {
if (!root) return [root,0]
var [left,ld] = dfs(root.left)
var [right,rd] = dfs(root.right)
if (ld > rd) return [left, ld + 1]
if (rd > ld) return [right,rd + 1]
return [root,ld + 1]
}
var res = dfs(root)
return res[0]
};