递归的题目，题目虽然说是深度但是我们用高度是一样的。递归的时候我们每次返回两个值，以当前node为根的最大高度h和当前子树的SSDN(Smallest Subtree with all the Deepest Nodes)。那么在每个节点我们要做的决策如下：
- 如果左子树的h大于右子树的h，我们要继续return左子树的h + 1和SSDN
- 如果右子树的h大于右子树的h，我们继续return右子树的h + 1和SSDN
- 如果左右子树h相等，我们return h + 1和当前节点
时间复杂度O(N)，代码如下:
No comments:
Post a Comment