目录
- 151. 反转字符串中的单词
- 129. 求根节点到叶节点数字之和
- 104. 二叉树的最大深度
- 101. 对称二叉树
- 110. 平衡二叉树
- 144. 二叉树的前序遍历
- 543. 二叉树的直径
- 48. 旋转图像
- 98. 验证二叉搜索树
- 39. 组合总和
151. 反转字符串中的单词
题目链接
class Solution:
def reverseWords(self, s: str) -> str:
ls=s.strip().split()
ls.reverse()
res=" ".join(ls)
return res
129. 求根节点到叶节点数字之和
题目链接
# 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 helper(self,root,i):
if not root:
return 0
temp=i*10+root.val
if not root.left and not root.right:
return temp
return self.helper(root.left,temp)+self.helper(root.right,temp)
def sumNumbers(self, root: Optional[TreeNode]) -> int:
return self.helper(root,0)
104. 二叉树的最大深度
题目链接
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
leftHight=self.maxDepth(root.left)
rightHigh=self.maxDepth(root.right)
return max(leftHight,rightHigh)+1
101. 对称二叉树
题目链接
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
def judge(left,right):
if not left and not right:
return True
elif not left or not right:
return False
elif left.val!=right.val:
return False
else:
return judge(left.left,right.right) and judge(left.right,right.left)
if not root:
return True
return judge(root.left,root.right)
110. 平衡二叉树
题目链接
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
# 二叉树的最大深度
def height(root):
if not root:
return 0
return max(height(root.left),height(root.right))+1
if not root:
return True
return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
144. 二叉树的前序遍历
题目链接
递归
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
lis=[]
def traversal(root):
if not root:
return
lis.append(root.val)
traversal(root.left)
traversal(root.right)
traversal(root)
return lis
非递归
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
white,gray=0,1
stack=[(white,root)]
res=[]
while stack:
color,node=stack.pop()
if node is None:
continue
if color==white:
stack.append((white,node.right))
stack.append((white,node.left))
stack.append((gray,node))
else:
res.append(node.val)
return res
543. 二叉树的直径
题目链接
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# 一条路径的长度为该路径经过的节点数减一，
# 所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一
self.max=0
def depth(root):
if not root:
return 0
left=depth(root.left)
right=depth(root.right)
self.max=max(self.max,left+right+1)
return max(left,right)+1
depth(root)
return self.max-1
48. 旋转图像
题目链接
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 用翻转代替旋转
# 先水平翻转再主对角线翻转即可得到将图像顺时针旋转90度的图像
n=len(matrix)
# 水平翻转
for i in range(n//2):
for j in range(n):
matrix[i][j],matrix[n-1-i][j]=matrix[n-1-i][j],matrix[i][j]
# 主对角线翻转
for i in range(n):
for j in range(i):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
98. 验证二叉搜索树
题目链接
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
# 中序遍历:左中右
self.pre=None
def dfs(root):
if not root:
return True
left=dfs(root.left)
if self.pre and self.pre.val>=root.val:
return False
self.pre=root
right=dfs(root.right)
return left and right
return dfs(root)
39. 组合总和
题目链接
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path=[]
res=[]
def backtracking(candidates,s,target,startIndex):
if s>target: # 要剪枝必须排序
return
if s==target:
res.append(path[:])
return
for i in range(startIndex,len(candidates)):
s+=candidates[i]
path.append(candidates[i])
backtracking(candidates,s,target,i) # 下一层i依然可以取到
s-=candidates[i]
path.pop()
candidates.sort()
backtracking(candidates,0,target,0)
return res
