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

类型：树

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

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

  ❓ 每个结点的深度是指根结点到该结点的距离。求树中所有最深结点的最近公共祖先。

  💡 两次 DFS

  我们先进行一次 DFS 计算并保存所有结点的深度，以找到所有的最深结点。

  在进行一次 DFS 通过回溯来找到这些最深结点的最近公共祖先。在这次 DFS 中需要处理以下情况：

  • node 没有左右子树，则返回 node。
  • node 的左右子树中都有最深结点，返回 node。
  • node 的左子树（或右子树）中含有最深结点，则递归 node 的左子树（或右子树）。
  • 以上都不符，说明当前子树中没有答案。

  class Solution(object):
      def subtreeWithAllDeepest(self, root):
          # Tag each node with it's depth.
          depth = {None: -1}
          def dfs(node, parent = None):
              if node:
                  depth[node] = depth[parent] + 1
                  dfs(node.left, node)
                  dfs(node.right, node)
          dfs(root)
  
          max_depth = max(depth.itervalues())
  
          def answer(node):
              # Return the answer for the subtree at node.
              if not node or depth.get(node, None) == max_depth:
                  return node
              L, R = answer(node.left), answer(node.right)
              return node if L and R else L or R
  
          return answer(root)

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 一次 DFS

  我们可以把上一方法中的两次 DFS 合成一次。

  在这个 DFS 中，我们使用后序遍历，即自底向上。我们自底向上地维护「当前」的最深深度，以及包含了这些最深结点的最近公共祖先，返回给上一层。

  在后序处理逻辑中，我们根据左右子树返回来的深度来处理当前结点的返回。

  • 如果左右子树的深度相同，那么我们将最深深度加一，并且将本结点作为「当前」所有最深结点的最近公共祖先返回给上一层。
  • 如果左子树的深度更深，那么显然右子树中的结点都不算是最深深度，我们将最深深度加一，并且将左子树作为「当前」所有最深结点的最近公共结点返回给上一层。
  • 如果右子树的深度更深，那么显然左子树中的结点都不算是最深深度，我们将最深深度加一，并且将右子树作为「当前」所有最深结点的最近公共结点返回给上一层。

  class Solution(object):
      def subtreeWithAllDeepest(self, root):
          # The result of a subtree is:
          # Result.node: the largest depth node that is equal to or
          #              an ancestor of all the deepest nodes of this subtree.
          # Result.dist: the number of nodes in the path from the root
          #              of this subtree, to the deepest node in this subtree.
          Result = collections.namedtuple("Result", ("node", "dist"))
          def dfs(node):
              # Return the result of the subtree at this node.
              if not node: return Result(None, 0)
              L, R = dfs(node.left), dfs(node.right)
              if L.dist > R.dist: return Result(L.node, L.dist + 1)
              if L.dist < R.dist: return Result(R.node, R.dist + 1)
              return Result(node, L.dist + 1)
  
          return dfs(root).node

  时间复杂度：O(n)，空间复杂度：O(n)