101.对称二叉树
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
# # 1.递归
# def twoTreeIsSymmetric(r1, r2):
# if not r1 and not r2:
# return True
# if not r1 or not r2:
# return False
# if r1.val != r2.val:
# return False
# return twoTreeIsSymmetric(r1.left, r2.right) and twoTreeIsSymmetric(r1.right, r2.left)
# if not root:
# return True
# return twoTreeIsSymmetric(root.left, root.right)
# 2.BFS 利用队列迭代 40ms
if not root:
return True
if not root.left and not root.right:
return True
if not root.left or not root.right:
return False
q = [(root.left, root.right)]
while q:
node1, node2 = q.pop(0)
if node1.val != node2.val:
return False
if node1.left and node2.right:
q.append((node1.left, node2.right))
elif node1.left or node2.right: # 有一个不存在
return False
if node1.right and node2.left:
q.append((node1.right, node2.left))
elif node1.right or node2.left:
return False
return True
102.二叉树的层次遍历（BST）
#1.利用两个列表，一个列表存当前层的val，一个列表存每一层的node
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans=[]
q=[root]
while q:
level_val=[]
next_node=[]
for item in q:
level_val.append(item.val)
if item.left:
next_node.append(item.left)
if item.right:
next_node.append(item.right)
q=next_node
ans.append(level_val)
return ans
#2.利用一个队列
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if not root:
return res
q = [root]
while q:
n = len(q)
layer = []
for _ in range(n):
node = q.pop(0)
layer.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(layer)
return res
104.树的最大深度
class Solution:
def maxDepth(self, root: TreeNode) -> int:
# # 1.递归 48ms
# if not root:
# return 0
# if not (root.left and root.right):
# return self.maxDepth(root.left)+self.maxDepth(root.right)+1
# return max(self.maxDepth(root.left), self.maxDepth(root.right))+1
# 2.DFS 30ms
if not root:
return 0
s = [(1, root)]
max_depth=0
while s:
depth, node = s.pop(-1)
if not node.left and not node.right:
max_depth=max(max_depth,depth)
if node.left:
s.append((depth+1, node.left))
if node.right:
s.append((depth+1, node.right))
return max_depth
# # 3.BFS 60ms
# if not root:
# return 0
# q = [(1, root)]
# max_depth = -float('inf')
# while q:
# depth, node = q.pop(0)
# if not node.left and not node.right:
# max_depth = max(max_depth, depth)
# if node.left:
# q.append((depth+1, node.left))
# if node.right:
# q.append((depth+1, node.right))
# return max_depth
105.从前序与中序遍历序列构造二叉树
##1.递归写法
class Solution:
#递归写法
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder and not inorder:
return None
root=TreeNode(preorder[0])
for i in range(len(inorder)):
if inorder[i]==preorder[0]:
left_inorder=inorder[:i]
right_inorder=inorder[i+1:]
left_preorder=preorder[1:1+i]
right_preorder=preorder[1+i:]
root.left=self.buildTree(left_preorder,left_inorder)
root.right=self.buildTree(right_preorder,right_inorder)
return root
144.树的前序遍历
# #1.递归写法 48ms
# res=[]
# def helper(r):
# if not r:
# return None
# res.append(r.val)
# helper(r.left)
# helper(r.right)
# helper(root)
# return res
# # 2.pythonic递归 40ms
# res = []
# if not root:
# return res
# res.append(root.val)
# res += self.preorderTraversal(root.left)
# res += self.preorderTraversal(root.right)
# return res
# # 3.迭代 40ms
# res = []
# if not root:
# return res
# s=[root]
# while s:
# node=s.pop(-1)
# res.append(node.val)
# if node.right:
# s.append(node.right)
# if node.left:
# s.append(node.left)
# return res
# # 4.pythonic 递归 48ms
# if not root:
# return []
# return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)
# #5.通用模板迭代 28ms
# res=[]
# s=[]
# cur=root
# while s or cur:
# while cur:
# res.append(cur.val)
# s.append(cur)
# cur=cur.left
# cur=s.pop(-1)
# cur=cur.right
# return res
# 6.标记法 双倍存储空间，模板相同 0表示未访问，1表示已访问 44ms
res = []
s = [(0, root)]
while s:
flag, cur = s.pop(-1)
if not cur:
continue
if flag == 0:
s.append((0, cur.right))
s.append((0, cur.left))
s.append((1, cur))
if flag == 1:
res.append(cur.val)
return res
236.二叉树的最近公共祖先
#1.递归写法，dfs遍历，当前节点和左右子树中有两个为true，则返回当前节点，即为最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.ans=None
def dfs(root):
if not root:
return False
left=dfs(root.left)
right=dfs(root.right)
mid=root==p or root==q
if mid+right+left>=2:
self.ans=root
return mid or left or right
dfs(root)
return self.ans
#2.用dic存储父节点
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
dic={root:None}
def bfs(root):
if root:
if root.left:
dic[root.left]=root
if root.right:
dic[root.right]=root
bfs(root.left)
bfs(root.right)
bfs(root)
l1,l2=p,q
while(l1!=l2):
l1=dic.get(l1) if l1 else q
l2=dic.get(l2) if l2 else p
return l1
网友评论