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

  • 树
  • 层序遍历

首先按照层序遍历将树按照层拆分成不同的集合。首先判断最后一层，即叶子节点层是否只有一个节点，如果只有一个节点则直接返回叶子节点。然后从倒数第二行开始往根方向遍历，判断当前层的孩子节点是否在往叶子节点方向的下一层。将当前层更新为满足孩子节点在下一层的节点集合。如果当前层只有一个节点满足条件，则直接返回该节点。

整体的思路类似于不断合并节点。找到最小公共父节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        rowList = list()
        rowSet = set()
        rowSet.add(root)
        rowList.append(rowSet)
        while(1):
            newRowSet = set()
            for each in rowSet:
                if each.left:
                    newRowSet.add(each.left)
                if each.right:
                    newRowSet.add(each.right)
            if newRowSet:
                rowList.append(newRowSet)
                rowSet = newRowSet
            else:
                break
        if len(rowList) == 1:
            return root
        lastSet = rowList[-1]
        if len(lastSet) == 1:
            return lastSet.pop()
        ans = None
        for i, eachSet in enumerate(rowList[-2::-1]):
            newLastSet = set()
            for eachNode in eachSet:
                if eachNode.left in lastSet or eachNode.right in lastSet:
                    newLastSet.add(eachNode)
            if len(newLastSet) == 1:
                ans = newLastSet.pop()
                return ans
            else:
                lastSet = newLastSet
        return ans;