admin 管理员组文章数量: 1086866
小黑公司团建吃烤肉肉啦，mac m1死活安装不上hbase，用拯救者一下就安上啦的leetcode之旅: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:self.max_depth = 0self.max_depth_nodes = []# 获得结点孩子数组def dfs(node, arr):if not node:returnarr.append(node)dfs(node.left, arr)dfs(node.right, arr)# 求二叉树每个节点的深度def get_depth(node, depth=0):if not node:returndepth += 1if depth > self.max_depth:self.max_depth_nodes = [node]self.max_depth = depthelif depth == self.max_depth:self.max_depth_nodes.append(node)get_depth(node.left, depth)get_depth(node.right, depth)get_depth(root)self.target_node = None# 后跟遍历，求最深公共结点def after_dfs(node):if not node:returnafter_dfs(node.left)after_dfs(node.right)if self.target_node:returnarr = []dfs(node,arr)flag = Truefor node_ in self.max_depth_nodes:if node_ not in arr:# print(node_,arr)flag = Falsebreakif flag:self.target_node = nodeafter_dfs(root)return self.target_node
两次深度优先
# 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:depth_map = {}self.max_depth = 0def dfs(node, depth):if not node:returndepth += 1if self.max_depth < depth:self.max_depth = depthdepth_map[node] = depthdfs(node.left, depth)dfs(node.right, depth)# 计算depth_mapdfs(root, 0)# 获取结果def result(node):if not node:return# 获取左右子树的包含max_depth的最小子树left_node = result(node.left)right_node = result(node.right)# 结点是最深结点if depth_map[node] == self.max_depth:return node# 左右子树都包含max_depth结点if left_node and right_node:return nodeif left_node:return left_nodeif right_node:return right_nodereturn Nonereturn result(root)
一次优先搜索
# 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 = rightclass Solution:def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:class Result(object):def __init__(self, node = None, dist = 0):self.node = nodeself.dist = distdef dfs(node):# 结点不存在if not node:return Result()left_result = dfs(node.left)right_result = dfs(node.right)# 左子树深的话，返回左子树下最深结点的最小子树if left_result.dist > right_result.dist:return Result(node=left_result.node, dist=left_result.dist + 1)if left_result.dist < right_result.dist:return Result(node=right_result.node, dist=right_result.dist + 1)return Result(node=node, dist=right_result.dist + 1)return dfs(root).node
小黑生活
发现了个学git的小神器
晚饭外卖
晚上开始哈农的学习
早餐牛排
早上运动
公司团建烤肉肉
午餐咖啡&&晚餐
晚间按摩一个半
早餐牛排&&跑步
午餐+聊天
复试被刷，遭遇了挫折，继续干!!!
感谢同事们的鼓励，大家一起加油。虽然我现在基础很差，也要干！！
本文标签： 小黑公司团建吃烤肉肉啦，mac m1死活安装不上hbase，用拯救者一下就安上啦的leetcode之旅865 具有所有最深节点的最小子树
版权声明：本文标题：小黑公司团建吃烤肉肉啦，mac m1死活安装不上hbase，用拯救者一下就安上啦的leetcode之旅:865. 具有所有最深节点的最小子树 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688028192a170552.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论