正文
最近，在进行python的相关学习，正好利用leetcode平台来验证自己的学习情况，今天分享的题目是leetcode上面的865题：求解 具有所有最深节点的最小子树 。
根据上面题目的描述，我们可以将我们的问题分为下面的几个步骤：
- 求解当前树的深度
- 获取到相同深度上的树节点
- 利用求解2个公共的父节点进行迭代
- 当返回结果集仅仅有一个结果的时候，说明我们得到了最后的返回结果
下面是实现的代码：
# 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 getDeep(self, root: TreeNode) -> int: if root is None: return 0 else: return max(self.getDeep(root.left), self.getDeep(root.right)) + 1 # 获取结果 def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode: deep = self.getDeep(root); if deep == 0: return None else: roots = [[] for x in range(deep)] self.dfs(root, roots, 0) res = roots[deep - 1] while len(res) != 1: p = res.pop() q = res.pop() common = self.commonNode(root, p, q) if common is not None: res.append(common) return res[0] # 获取公共节点的方法 def commonNode(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: if root is None or p.val == root.val or q.val == root.val: return root left = self.commonNode(root.left, p, q) right = self.commonNode(root.right, p, q) if left is None: return right if right is None: return left return root # 深度优先搜索树 def dfs(self, root: TreeNode, roots: list, deep: int): if root is not None: roots[deep].append(root) self.dfs(root.left, roots, deep + 1) self.dfs(root.right, roots, deep + 1)
