111. Minimum Depth of Binary Tree (Easy)
Given a binary tree, find its minimum depth.
# 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:
# 2
# 3
# 4
# 5
# 6
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
min_ = float('inf')
if root.left:
min_ = min(min_,self.minDepth(root.left))
if root.right:
min_ = min(min_,self.minDepth(root.right))
if not root.left and not root.right:
min_=0
return 1+min_
#answer way of writting
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if root.left is None:
return self.minDepth(root.right)+1
if root.right is None:
return self.minDepth(root.left)+1
return min(self.minDepth(root.left),self.minDepth(root.right))+1
注意special case 全是右斜。 直接写成 if not root: return 0 ， return 1+min(self.minDepth(root.left),self.minDepth(root.right))是不对的。全右斜情况root.left直接是空，所以会返回0+1. 应该多一个判断，左右子树是否存在，存在再更新值。
112. Path Sum （Easy）
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root: return False
if (not root.left) and not (root.right) and (targetSum==root.val):
return True
if (not root.left) and not (root.right) and (targetSum!=root.val):
return False
return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
113. Path Sum II (Medium)
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
if not root: return res
def ps(root,target,tmp):
if not root.left and not root.right and root.val==target:
tmp.append(root.val)
res.append(tmp[:])
if root:
tmp.append(root.val)
if root.left:
ps(root.left,target-root.val,tmp[:])
if root.right:
ps(root.right,target-root.val,tmp[:])
ps(root,targetSum,[])
return res
定义帮助函数保存path。
114. Flatten Binary Tree to Linked List （Medium）
Given the root of a binary tree, flatten the tree into a "linked list"
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
# 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 flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
previous = None
def pre(node):
nonlocal previous
if not node: return
if previous:
previous.left = None
previous.right = node
previous = node
nodeleft = node.left
noderight = node.right
pre(nodeleft)
pre(noderight)
pre(root)
return root
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
res = []
stack = []
head=None
cur=None
while root or stack:
while root:
res.append(root)
stack.append(root)
root=root.left
node = stack.pop()
root=node.right
pre=None
for node in res:
if pre:
pre.left = None
pre.right = node
pre = node
if pre:
pre.left=None
115. Distinct Subsequences (Hard)
Given two strings s and t, return the number of distinct subsequences of s which equals t
class Solution:
def numDistinct(self, s: str, t: str) -> int:
if len(t)>len(s): return 0
m=len(t)
n=len(s)
dp=[[0]*(n+1) for _ in range(m+1)]
# fill row 0:
for i in range(n+1):
dp[0][i]=1
for i in range(1,m+1):
for j in range(1,n+1):
if t[i-1]==s[j-1]:
dp[i][j]=dp[i-1][j-1]+dp[i][j-1]
else:
dp[i][j]=dp[i][j-1]
return dp[m][n]
# S
# # b a b g b a g
# T # 1 1 1 1 1 1 1 1
# b 0 1 1 2 2 3 3 3
# a 0 0 1 1 1 1 4 4
# g 0 0 0 0 1 1 1 5
感觉应该用dp做。找递推关系。。。。
如果s和t末尾字符一样， dp[i][j] = dp[i-1][j-1] + dp[i][j-1] 是t，s都drop末尾+只有s drop末尾，因为是t去匹配s。 如果s和末尾字符不一样 dp[i][j] = dp[i][j-1]。 注意初始条件，空字符串匹配s可能的方式为1.
116. Populating Next Right Pointers in Each Node （Medium）
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root: return root
queue = [root]
while queue:
level=[]
l=len(queue)
for _ in range(l):
cur = queue.pop(0)
level.append(cur)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
pre=None
for node in level:
if pre:
pre.next=node
pre = node
return root
bfs level order transversal ...
117. Populating Next Right Pointers in Each Node II (Medium)
解决方法同上
118. Pascal's Triangle （Easy）
Given an integer numRows, return the first numRows of Pascal's triangle.
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows==1:
return [[1]]
if numRows==2:
return [[1],[1,1]]
res = [[1],[1,1]]
for _ in range(numRows-2):
level = [1,]
prev_level = res[-1]
for i in range(len(prev_level)-1):
val = prev_level[i]+prev_level[i+1]
level.append(val)
level.append(1)
res.append(level)
return res
杨辉三角
119. Pascal's Triangle II （Easy）
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [1]*(rowIndex+1)
if rowIndex<=1:
return res
for i in range(rowIndex):
length = 2+i
res_copy = res[:]
for j in range(1,length-1):
res[j]=res_copy[j]+res_copy[j-1]
return res
还是杨辉三角，要细心。
120. Triangle （Medium）
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
def mintotal(triangle, i):
if not triangle:
return 0
root = triangle[0][i]
triangle.pop(0)
return root+min(mintotal(triangle[:],i),mintotal(triangle[:],i+1))
return mintotal(triangle,0)
# second pass solution
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
mem=dict()
def mintotal(triangle, i,level):
if (level,i) in mem: return mem[(level,i)]
if not triangle:
return 0
root = triangle[0][i]
triangle.pop(0)
res= root+min(mintotal(triangle[:],i,level+1),mintotal(triangle[:],i+1,level+1))
mem[(level,i)]=res
return res
return mintotal(triangle,0,0)
#answer way of writting
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
rows=len(triangle)
minlen=triangle[-1][:]
for layer in range(rows-2,-1,-1):
for i in range(layer+1):
minlen[i]=min(minlen[i],minlen[i+1])+triangle[layer][i]
return minlen[0]
first try, time limit exceeded. add mem, nailed it. 答案用DP方法也很巧妙，因为最后一行就是所有可能性，慢慢回溯去求结果。root是 minlen[0].