leetcode 866 Smallest Subtree with all the Deepest Nodes

发表于 |

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.
A node is deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is that node, plus the set of all descendants of that node.
Return the node with the largest depth such that it contains all the deepest nodes in it’s subtree.

题目描述

分析：

  1. 标准的bfs问题，我们只需要记录最后一层的所有节点，然后获取他们的父节点，依次类推，当父节点的数量只有1个时，说明找到了最后所求
  2. bfs中队列存储数据格式为(node,parent_node)，初始化为(root,None),让我们用字典能建立对应关系!

思路：

  1. 我们在用bfs遍历时，用一个字典记录下结点与其父节点的对应关系，并用一个列表记录下每一层的所有结点，当bfs遍历结束时，列表中所存结点即为最后一层结点
  2. 对列表中结点进行迭代，用一个集合来记录父节点，当集合长度为1时，循环结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def subtreeWithAllDeepest(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        Q = collections.deque([(root,None)])
        d = {}
        while Q:
            iters = len(Q)
            rec = []
            for i in range(iters):
                a,b = Q.popleft()
                rec.append(a)
                if a.left: Q.append((a.left,a))
                if a.right: Q.append((a.right,a))
                # 建立对应关系
                d[a] = b
        # rec records the last level node
        s = set(rec)
        res = []
        while len(s) != 1:
            s = set()
            for node in rec:
                s.add(d[node])
            res += rec
            rec = list(s)
        return list(s)[0]

57 / 57 test cases passed.
difficulty: medium
Runtime: 24 ms