小黑除夕跟尚香吃喜茶喝火锅,走了一下午,晚上休息会儿顺便的leetcode之旅:剑指 Offer 34. 二叉树中和为某一值的路径
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
小黑代码
# 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 pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
paths = []
def dfs(node, path = []):
# 递归出口
if not node:
return
path.append(node.val)
# 递归出口
if not (node.left or node.right) and sum(path) == target:
paths.append(path[:])
dfs(node.left)
dfs(node.right)
path.pop()
dfs(root)
return paths
层次遍历法
# 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 pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
if not root:
return []
# 初始化队列
q = collections.deque([root])
q_sum = collections.deque([root.val])
# node:parent
map_ = collections.defaultdict(lambda:None)
arr = []
while q:
# 出队
top = q.popleft()
top_num = q_sum.popleft()
# 判断是否叶子结点并输出结点
if not (top.left or top.right) and top_num == target:
arr.append(top)
continue
# 入队操作
if top.left:
q.append(top.left)
q_sum.append(top.left.val + top_num)
map_[top.left] = top
if top.right:
q.append(top.right)
q_sum.append(top.right.val + top_num)
map_[top.right] = top
# 输出路径
results = []
for node in arr:
path = []
while node:
path.append(node.val)
node = map_[node]
results.append(path[::-1])
return results
小黑生活
150分钟的华为od算法机试感觉还可以
年前最后一天的公司和地铁
最近好多销售岗位给我发信息呢
下了地铁吃个好利来然后去练琴,然后去吃麦当劳
今天大年三十跟尚香(小*林)出去吃新辣道
喝了喜茶
看到了acm车牌号的车
又溜了一下午弯