二叉树的前序遍历：根-左-右
题目描述
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if not root:returnres.append(root.val)dfs(root.left)dfs(root.right)dfs(root)return res
二叉树的中序遍历：左-中-右
题目描述
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if not root:returndfs(root.left)res.append(root.val)dfs(root.right)dfs(root)return res
二叉树的后续遍历：左-右-中
题目描述
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if not root:returndfs(root.left)dfs(root.right)res.append(root.val)dfs(root)return res
二叉树的层序遍历
题目描述
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []res = []#创建一个双端队列，并将根节点加入到队列queue = collections.deque()queue.append(root)while queue:tmp = []#循环遍历当前层的节点，for循环，循环次数是当前队列的长度（即当前层的节点数）for _ in range(len(queue)):#从队列的左侧弹出一个节点，赋值给node。使用popleft()方法是因为我们要进行广度优先遍历，每次处理队列中的第一个节点。node = queue.popleft()tmp.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)res.append(tmp)return res
二叉树的最大深度
题目描述
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0else:left_max = self.maxDepth(root.left)right_max = self.maxDepth(root.right)return max(left_max, right_max) + 1
对称二叉树
题目描述
class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:def isMirror(node1: TreeNode, node2: TreeNode) -> bool:if not node1 and not node2:return Trueif not node1 or not node2 or node1.val != node2.val:return Falsereturn isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left)return isMirror(root, root)
路径总和
题目描述
class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return Falseif not root.left and not root.right: ## 如果当前节点为叶子节点，检查当前节点值是否等于目标和return root.val == targetSum# 递归检查左子树和右子树return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
从中序与后序遍历序列构造二叉树
题目描述
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:if not inorder or not postorder:return None# 后序遍历的最后一个节点是根节点root_val = postorder[-1]root = TreeNode(root_val)# 在中序遍历中找到根节点的位置root_index_inorder = inorder.index(root_val)# 切割中序和后序遍历，得到左子树和右子树的中序和后序遍历inorder_left = inorder[:root_index_inorder]inorder_right = inorder[root_index_inorder+1:]postorder_left = postorder[:root_index_inorder]postorder_right = postorder[root_index_inorder:-1]# 递归构建左子树和右子树root.left = self.buildTree(inorder_left, postorder_left)root.right = self.buildTree(inorder_right, postorder_right)return 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 = right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder or not inorder:return Noneroot_value = preorder[0]root = TreeNode(root_value)root_index_inorder = inorder.index(root_value)inorder_left = inorder[:root_index_inorder]inorder_right = inorder[root_index_inorder+1:]preorder_left = preorder[1:1+len(inorder_left)]preorder_right = preorder[1+len(inorder_left):]root.left = self.buildTree(preorder_left, inorder_left)root.right = self.buildTree(preorder_right, inorder_right)return root
填充每个节点的下一个右侧节点指针
题目描述
"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':if not root:# 如果根节点为空，则无需处理，直接返回return root# 初始化一个队列，将根节点入队queue = [root]while queue:# 获取当前层的节点数量size = len(queue)prev = None # 用于记录上一个处理的节点，以便设置next指针# 遍历当前层的所有节点for _ in range(size):node = queue.pop(0) # 从队列中取出一个节点if prev:# 如果prev不为空，说明不是该层的第一个节点，需要设置prev的next指针prev.next = node# 如果当前节点有左子节点，则将左子节点加入队列if node.left:queue.append(node.left)# 如果当前节点有右子节点，则将右子节点加入队列if node.right:queue.append(node.right)prev = node # 更新prev为当前节点，以便下次循环时设置next指针return root # 返回处理后的根节点二叉树的最近公共祖先
题目描述
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root == p or root == q: return root # 在左子树和右子树中分别寻找p和q节点left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q)# 如果left和right都不为空，说明p和q分别位于当前节点的左右两侧，所以当前节点就是最近公共祖先if left and right: return root # 如果left为空，则返回right；反之返回left# 这个返回值的含义是：如果在某个方向上没有找到目标节点，则返回空；否则返回找到的目标节点或它们的公共祖先节点return left if left else right
二叉树的序列化与反序列化
题目描述
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Codec:def serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str""""""序列化二叉树为字符串。使用前序遍历，空节点用特殊字符表示，如'#'。"""def helper(node):if node is None:values.append('#')else:values.append(str(node.val))helper(node.left)helper(node.right)values = []helper(root)return ' '.join(values)def deserialize(self, data):"""Decodes your encoded data to tree.:type data: str:rtype: TreeNode""""""根据序列化的字符串反序列化二叉树。"""def helper():val = next(vals)if val == '#':return Nonenode = TreeNode(int(val))node.left = helper()node.right = helper()return nodevals = iter(data.split())return helper()
