目录
- 前言
- 一、前序遍历
- 二、中序遍历
- 三、后序遍历
- 四、层次遍历
- 4.0、层次框架模板
- 4.1、经典题目
- leetcode107. 二叉树的层序遍历 II
- leetcode103. 二叉树的锯齿形层序遍历
- leetcode513. 找树左下角的值
- leetcode104. 二叉树的最大深度
- leetcode111. 二叉树的最小深度
- leetcode515. 在每个树行中找最大值
- leetcode199. 二叉树的右视图
- leetcode637. 二叉树的层平均值
- leetcode429. N 叉树的层序遍历
- leetcode226. 翻转二叉树
- leetcode剑指 Offer 28. 对称的二叉树
- leetcode958. 二叉树的完全性检验（判断一颗二叉树是否是完全二叉树）
- leetcode116. 填充每个节点的下一个右侧节点指针
- leetcode117. 填充每个节点的下一个右侧节点指针 II
- 总结
- Reference
前言
整理了下二叉树遍历相关的题目，大概40道左右。所有的题目都是使用前序、中序、后序的递归、迭代法；层次遍历的迭代法。熟练使用这七种框架式的写法，在框架之上修改下逻辑，80%的二叉树的题目都可以解决。
一、前序遍历
1.0、前序框架模板
leetcode144. 二叉树的前序遍历
递归写法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
迭代写法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
res.append(cur.val)
cur = cur.left
cur = stack.pop()
cur = cur.right
return res
1.1、经典题目
要点
1、找到叶子节点：if not node.left and not node.right
2、找到左叶子节点：if node.left and not node.left.left and not node.left.right
3、找到最大深度的第一个叶子节点: if not node.left and not node.right and curDepth > maxDepth
leetcode257. 二叉树的所有路径
# 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 binaryTreePaths(self, root: TreeNode) -> List[str]:
res = []
def dfs(node, path):
# 碰到空节点，递归结束
if not node: return
# 叶子节点 将当前路径append进res中
if not node.left and not node.right:
res.append(path + str(node.val))
# 不是叶子节点的话，就递归调用左右子树
dfs(node.left, path + str(node.val) + '->')
dfs(node.right, path + str(node.val) + '->')
dfs(root, '')
return res
leetcode226. 翻转二叉树
226. 翻转二叉树 = 剑指 Offer 27. 二叉树的镜像：前序 / 层次
# 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 invertTree(self, root: TreeNode) -> TreeNode:
# 1、前序遍历
def dfs(node):
# 空节点，递归结束
if not node: return
# 不是空节点（左右子树都不为空/左子树不为空+右子树为空/左子树为空+右子树不为空），就调换左右子树
node.left, node.right = node.right, node.left
# 递归调用左右子树
dfs(node.left)
dfs(node.right)
dfs(root)
return root
# 2、层次遍历
if not root: return None
queue = [root]
while queue:
cur = queue.pop(0)
cur.left, cur.right = cur.right, cur.left
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return root
leetcode129. 求根节点到叶节点数字之和
# 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
# 核心要点： path_sum * 10 + root.val
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
res = 0
def dfs(node, path_sum):
# res定义成了一个nonlocal变量
# nonlocal关键字修饰变量后标识该变量是上一级函数中的局部变量，如果上一级函数中不存在该局部变量，nonlocal位置会发生错误
nonlocal res
# 空节点，递归结束
if not node: return
# 碰到叶子节点 就将结果存入res中
if not node.left and not node.right:
res += path_sum * 10 + node.val
# 递归调用左右子树，每下去一层，要乘10+当前节点的val
dfs(node.left, path_sum * 10 + node.val)
dfs(node.right, path_sum * 10 + node.val)
dfs(root, 0)
return res
leetcode404. 左叶子之和
404. 左叶子之和： 前序
# 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 sumOfLeftLeaves(self, root: TreeNode) -> int:
res = 0
def dfs(node):
# res定义成了一个nonlocal变量
# nonlocal关键字修饰变量后标识该变量是上一级函数中的局部变量，如果上一级函数中不存在该局部变量，nonlocal位置会发生错误
nonlocal res
# 空节点，递归结束
if not node: return
# 找到每一个左叶子节点
if node.left and not node.left.left and not node.left.right:
res += node.left.val
# 递归调用左右子树
dfs(node.left)
dfs(node.right)
dfs(root)
return res
leetcode513. 找树左下角的值
513. 找树左下角的值：层次 / 前序
# 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 findBottomLeftValue(self, root: TreeNode) -> int:
# 1、层次遍历
queue = [root]
res = root.val
while queue:
# 计算当前层的节点个数
size = len(queue)
# 遍历每一层的所有节点
for i in range(size):
cur = queue.pop(0)
# i==0: 每一层的第一个节点
if i == 0: res = cur.val
# 将左右节点加入queue中
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res
# 2、前序遍历
maxDepth, mostLeft = 0, root.val
def dfs(node, curDepth):
# cur_depth来记录叶子节点所在的层数
nonlocal maxDepth, mostLeft
# 碰到空节点，递归结束
if not node: return
# 找到叶子节点且当前深度大于最大深度，更新maxDepth和mostLeft
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
mostLeft = node.val
# 递归调用左右子树 深度+1
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
dfs(root, 0)
return mostLeft
leetcode112. 路径总和
112. 路径总和：前序
# 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:
has_path = False
def dfs(node, path_sum):
# 这一步很重要，如果没有这一步的话，会直接返回False
nonlocal has_path
# 碰到空节点，递归结束
if not node: return
# 叶子节点且所有节点值相加等于targetSum
if not node.left and not node.right:
if path_sum + node.val == targetSum:
has_path = True
return
# 递归调用左右子树
dfs(node.left, path_sum + node.val)
dfs(node.right, path_sum + node.val)
dfs(root, 0)
return has_path
leetcode113. 路径总和 II
113. 路径总和 II： 前序
# 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 = []
def dfs(node, path_sum, path):
# 碰到空节点，递归结束
if not node: return
# 叶子节点且从根节点到叶子节点路径总和等于给定目标和
if not node.left and not node.right:
if path_sum + node.val == targetSum:
path.append(node.val)
res.append(path)
# 注意这里不能用path.append(node.val)
# a = [1, 2]
# b = [3]
# print(a + b) # [1, 2, 3]
# a = [1, 2]
# print(a.append(3)) # None
dfs(node.left, path_sum + node.val, path + [node.val])
dfs(node.right, path_sum + node.val, path + [node.val])
dfs(root, 0, [])
return res
leetcode437. 路径总和 III
437. 路径总和 III：前序 / 前缀和
# 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, targetSum: int) -> int:
if not root: return 0
# 以root为根节点 查询所有符合的路径数目
def dfs(node, path_num):
if not node: return 0
res = 0
if path_num + node.val == targetSum:
res += 1
res += dfs(node.left, path_num + node.val)
res += dfs(node.right, path_num + node.val)
return res
# root + root.left + root.right
return dfs(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)
二、中序遍历
2.0、中序框架模板
leetcode94. 二叉树的中序遍历
递归写法和迭代写法
# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
# 1、递归法
res = []
def dfs_in(node):
nonlocal res
if not node: return
dfs_in(node.left)
res.append(node.val)
dfs_in(node.right)
dfs_in(root)
return res
# 2、迭代法
stack, cur = [], root
res = []
while stack or cur:
# 一直往下走 走到最左边的节点
while cur:
stack.append(cur)
cur = cur.left
# pop出当前子树的最左边节点
cur = stack.pop()
res.append(cur.val)
# 再继续遍历右子树 -> 执行while cur 找到右子树的最左节点...
cur = cur.right
return res
2.1、经典题目
中序遍历的一个大应用就是和二叉搜索树结合起来的。
leetcode98. 验证二叉搜索树
# 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: TreeNode) -> bool:
# 1、中序遍历迭代法
stack, cur = [], root
# 初始化pre值为一个最小的数 这样才能保证pre一定比第一个数更小 符合二叉搜索树
preValue = float('-inf')
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
# 如果中序遍历的当前值(cur.val)比之前的值(preValue)更小(或相等) 说明这棵树不是二叉搜索树
if cur.val <= preValue:
return False
# 向后移动（类似链表）
preValue = cur.val
cur = cur.right
return True
# 2、中序遍历递归法
# 原理和上面的迭代法一样
preValue = float('-inf')
res = True
def dfs_in(node):
nonlocal preValue, res
if not node: return
dfs_in(node.left)
if node.val <= preValue:
res = False
return
preValue = node.val
dfs_in(node.right)
dfs_in(root)
return res
leetcode230. 二叉搜索树中第K小的元素
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# 1、中序迭代法
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
# 找到一个最小节点 k值就减1
k -= 1
# 因为是先减再比较的 所以条件就变成了k==0
if k == 0: return cur.val
# 或者也可以写成这样
# if k == 1: return cur.val
# k -= 1
cur = cur.right
leetcode剑指 Offer 54. 二叉搜索树的第k大节点
和上一题差不多，从小到大遍历换成从大到小遍历即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.right
cur = stack.pop()
k -= 1
if k == 0: return cur.val
cur = cur.left
leetcode530. 二叉搜索树的最小绝对差
# 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 getMinimumDifference(self, root: TreeNode) -> int:
minV = float('inf') # 初始化最小绝对差
preV = float('inf') # 初始化前一节点的值
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
# 计算当前节点val和前一节点val的绝对值
curV = abs(cur.val - preV)
# 比较 变换minV
if curV < minV:
minV = curV
# 先前移动 类似链表的感觉
preV = cur.val
cur = cur.right
return minV
leetcode501. 二叉搜索树中的众数
# 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 findMode(self, root: TreeNode) -> List[int]:
# 1、先统计 再更新 直接将二叉搜索树中的所有val和出现的次数存放到字典中 再读出来即可
stack, cur = [], root
# 如果键k没在字典里会自动添加k且默认value=0
count_dict = defaultdict(int)
maxCount = 0
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
# 将当前节点val对应于字典key相关的val+1 如果不存在就自动添加0+1=1
count_dict[cur.val] += 1
# 更新目前为止出现的最大次数（众数次数）
if count_dict[cur.val] > maxCount:
maxCount = count_dict[cur.val]
cur = cur.right
# 返回所有总数（v=众数次数）
return [k for k, v in count_dict.items() if v == maxCount]
上面只写了一种先统计再更新的中序遍历方法，还有一种边统计边更新的方法，有想法的可以自己看下：
leetcode538. 把二叉搜索树转换为累加树
# 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 convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack, cur = [], root
count = 0
while stack or cur:
while cur:
stack.append(cur)
cur = cur.right # 从大到小
cur = stack.pop()
# 累加再更新val
count += cur.val
cur.val = count
cur = cur.left
return root
leetcode426. 将二叉搜索树转化为排序的双向链表
剑指 Offer 36. 二叉搜索树与双向链表 = 426. 将二叉搜索树转化为排序的双向链表（重要）
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root: return None
stack, cur = [], root
pre, head = None, None
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
# pre = None的话 表明刚好遍历到二叉搜索树的最小节点 用head标记（方便后面首尾连接）
# 第一个位置不需要相连 标记即可
if not pre:
head = cur
# 从第二个位置开始 pre和cur相连
else:
pre.right = cur
cur.left = pre
# pre和cur向后移动 类似于链表
pre = cur
cur = cur.right
# 首尾相连
pre.right = head
head.left = pre
return head
三、后序遍历
3.0、后序框架模板
leetcode145. 二叉树的后序遍历
递归写法
# 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 postorderTraversal(self, root: TreeNode) -> List[int]:
# 1、递归 后序：左右根
res = []
def dfs(node):
if not node: return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
迭代写法
# 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 postorderTraversal(self, root: TreeNode) -> List[int]:
# 2、迭代 后序：左右根 -> 根右左 -> reverse
stack, cur = [], root
res = []
while stack or cur:
while cur:
stack.append(cur)
res.append(cur.val)
cur = cur.right
cur = stack.pop()
cur = cur.left
return res[::-1]
3.1、经典题目
leetcode226. 翻转二叉树
这道题可以用层次遍历、前序遍历、后序遍历三种方法。但是唯独不能用中序遍历，因为根据左根右的顺序，在遍历根的时候，如果调换左右节点，顺序就会乱掉。
# 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 invertTree(self, root: TreeNode) -> TreeNode:
# 1、前序遍历
def dfs(node):
# 空节点，递归结束
if not node: return
# 不是空节点（左右子树都不为空/左子树不为空+右子树为空/左子树为空+右子树不为空），就调换左右子树
node.left, node.right = node.right, node.left
# 递归调用左右子树
dfs(node.left)
dfs(node.right)
dfs(root)
return root
# 2、层次遍历
if not root: return None
queue = [root]
while queue:
cur = queue.pop(0)
cur.left, cur.right = cur.right, cur.left
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return root
# 3、后序遍历
def dfs(node):
# 空节点，递归结束
if not node: return
# 递归调用左右子树
dfs(node.left)
dfs(node.right)
# 不是空节点（左右子树都不为空/左子树不为空+右子树为空/左子树为空+右子树不为空），就调换左右子树
node.left, node.right = node.right, node.left
dfs(root)
return root
leetcode104. 二叉树的最大深度
这道题可以用层次遍历、前序遍历、中序遍历、后序遍历四种方法。
# 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: TreeNode) -> int:
# 1、层次遍历
if not root: return 0
queue = [root]
depth = 0
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
depth += 1
return depth
# 2、先序遍历
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
dfs(root, 1)
return maxDepth
# 3、中序遍历
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
dfs(node.left, curDepth + 1)
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(node.right, curDepth + 1)
dfs(root, 1)
return maxDepth
# 4.1、后序遍历1
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(root, 1)
return maxDepth
# 4.2、后序遍历2
def dfs(node):
if not node: return 0
leftD = dfs(node.left)
rightD = dfs(node.right)
return max(leftD, rightD) + 1
return dfs(root)
leetcode559. N 叉树的最大深度
这道题有前序、后序、层次遍历三种解法。没用中序遍历，因为N叉树没有中序而言。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
# 1、前序遍历
if not root: return 0
maxD = float('-inf')
def dfs(node, curD):
nonlocal maxD
if not node: return 0
if not node.children and curD > maxD:
maxD = curD
for c in node.children:
dfs(c, curD + 1)
dfs(root, 1)
return maxD
# 2、后序遍历
if not root: return 0
maxD = float('-inf')
def dfs(node, curD):
nonlocal maxD
if not node: return 0
for c in node.children:
dfs(c, curD + 1)
if not node.children and curD > maxD:
maxD = curD
dfs(root, 1)
return maxD
# 3、层次遍历
if not root: return 0
queue, depth = [root], 0
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
for c in cur.children:
queue.append(c)
size -= 1
depth += 1
return depth
leetcode111. 二叉树的最小深度
这道题和上面的 104. 二叉树的最大深度 差不多，将 maxDepth 改成 minDepth 即可，同样有前、中、后、层次遍历4种方法。
# 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 minDepth(self, root: TreeNode) -> int:
# 1、层次遍历
if not root: return 0
queue = [root]
depth = 1
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
# 一层层遍历 只要出现第一个叶子节点 就直接返回深度 即要求的最小深度
if not cur.left and not cur.right:
return depth
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
depth += 1
# 2、先序遍历
if not root: return 0
minD = float('inf')
def dfs(node, curD):
nonlocal minD
if not node: return 0
if not node.left and not node.right and curD < minD:
minD = curD
dfs(node.left, curD + 1)
dfs(node.right, curD + 1)
dfs(root, 1)
return minD
# 3、中序遍历
if not root: return 0
minD = float('inf')
def dfs(node, curD):
nonlocal minD
if not node: return 0
dfs(node.left, curD + 1)
if not node.left and not node.right and curD < minD:
minD = curD
dfs(node.right, curD + 1)
dfs(root, 1)
return minD
# 4、后序遍历
if not root: return 0
minD = float('inf')
def dfs(node, curD):
nonlocal minD
if not node: return 0
dfs(node.left, curD + 1)
dfs(node.right, curD + 1)
if not node.left and not node.right and curD < minD:
minD = curD
dfs(root, 1)
return minD
leetcode543. 二叉树的直径 （重要）
这道题必须使用后序遍历，因为要想得到最长直径，必须从叶子节点往上算，计算每个节点的左右哪条路径最长。
# 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: TreeNode) -> int:
# 后序遍历
max_path = 0
def dfs_post(node):
nonlocal max_path
if not node: return 0
# 当前节点左子树的最长路径的节点个数
leftD = dfs_post(node.left)
# 当前节点右子树的最长路径的节点个数
rightD = dfs_post(node.right)
# 当前节点左子树的最长路径节点个数 + 当前节点右子树的最长路径节点个数 + 当前节点 = 整棵树的最长路径节点个数
max_path = leftD + rightD + 1
# 返回以当前节点为根节点的最长路径的节点个数 1=当前节点
return max(leftD, rightD) + 1
dfs_post(root)
# 直径 = 最长路径 = 最长路径节点个数 - 1
return max_path - 1
leetcode124. 二叉树中的最大路径和（重要）
这道题和上一道题很像，一样的套路。
# 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 maxPathSum(self, root: TreeNode) -> int:
# 初始化最大路径和 很小的数 因为 -1000 <= Node.val <= 1000
maxSum = float('-inf')
def dfs_post(node):
nonlocal maxSum
# 碰到空节点 停止递归
if not node: return 0
# 计算左子树最大路径和 只要左子树的路径和大于0才会选取当前左子树作为最大路径
leftMax = max(dfs_post(node.left), 0)
# 计算右子树最大路径和
rightMax = max(dfs_post(node.right), 0)
# 最大路径和 = max(左右子树最大路径和 + 当前节点的val, maxSum)
maxSum = max(leftMax + rightMax + node.val, maxSum)
# 返回以当前节点为根节点的树的最大路径和
return max(leftMax, rightMax) + node.val
dfs_post(root)
return maxSum
leetcode222. 完全二叉树的节点个数
# 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 countNodes(self, root: TreeNode) -> int:
# 1、层次遍历 时间复杂度O(n)
if not root: return 0
queue = [root]
count = 0
while queue:
cur = queue.pop(0)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
# 层次遍历很简单 直接遍历一个 (count+1) 即可
count += 1
return count
# 2、前序遍历 时间复杂度O(n)
count = 0
def dfs(node):
nonlocal count
if not node: return
count += 1
dfs(node.left)
dfs(node.right)
dfs(root)
return count
# 3、中序遍历 时间复杂度O(n)
count = 0
def dfs(node):
nonlocal count
if not node: return
dfs(node.left)
count += 1
dfs(node.right)
dfs(root)
return count
# 4、后序遍历 时间复杂度O(n)
count = 0
def dfs(node):
nonlocal count
if not node: return
dfs(node.left)
dfs(node.right)
count += 1
dfs(root)
return count
# 5、时间复杂度O(logn)
if not root: return 0
# 计算一颗完全二叉树的高度
def getH(node):
height = 0
while node:
height += 1
node = node.left
return height
# 计算当前节点的左右子树的高度
leftH, rightH = getH(root.left), getH(root.right)
# 如果左右子树高度相同 那么左子树是一颗满二叉树 右子树仍是一颗完全二叉树 继续递归调用右子树
if leftH == rightH:
return 2**leftH - 1 + self.countNodes(root.right) + 1
# 如果左子树高度>右子树高度 那么右子树是一颗满二叉树 左子树仍是一颗完全二叉树 继续递归调用左子树
else:
return self.countNodes(root.left) + 2**rightH - 1 + 1
leetcode814. 二叉树剪枝
# 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 pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return None
def has_one(node):
# 空节点 递归结束
if not node: return False
# 调用左右子树
left = has_one(node.left)
right = has_one(node.right)
# 如果左子树没有val=1的节点 左子树直接为None
if left == False: node.left = None
# 如果右子树没有val=1的节点 右子树直接为None
if right == False: node.right = None
# 返回以node为根节点的树有没有val=1的节点(根节点/左子树/右子树有一个val=1，那么整棵树就有val=1的节点)
return True if left or right or node.val == 1 else False
return root if has_one(root) else None
leetcode110. 平衡二叉树（重要 经典）
# 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: TreeNode) -> bool:
# 1、前序遍历 时间复杂度 O(nlogn)
# 有很多重复计算 比如计算高度 计算了root的高度 再计算root左右子树的高度 这其中是有很多重复的计算的
if not root: return True
# 求一棵树的高度
def height(node):
if not node: return 0
leftH = height(node.left)
rightH = height(node.right)
return max(leftH, rightH) + 1
# 求root的左子树和右子树高度
left, right = height(root.left), height(root.right)
# 一棵树root要满足平衡二叉树 = root是平衡二叉树 + root.left是平衡二叉树 + root.right是平衡二叉树
return abs(left - right) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
# 2、优化方法：后序遍历 + 剪枝 时间复杂度 O(n)
# 边求高度 边进行判断
def balance(node):
# 当且节点为None 返回高度为0
if not node: return 0
# 求当前节点的左子树高度
left = balance(node.left)
# 如果当前树的左子树不是平衡二叉树 那么不用再算了 当前树也一定不是平衡二叉树
if left == - 1: return -1
# 求当前节点的右子树高度
right = balance(node.right)
# 如果当前树的右子树不是平衡二叉树 那么不用再算了 当前树也一定不是平衡二叉树
if right == -1: return -1
# 判断以当前节点为根节点的树是否是平衡二叉树 如果是就返回当前树的高度 否则返回-1
return max(left, right) + 1 if abs(left - right) <= 1 else -1
return isBalanced(node) != -1
leetcode236. 二叉树的最近公共祖先（很重要 难点 经典）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 方法1、后序遍历
# # 递归出口 1)当前这棵子树的root不是p或q 就直接返回None 2)当前这棵子树的root是p或q 直接返回p或q
# if root in (p, q, None): return root
# # 递归调用左右子树 继续在左右子树中查找有没有p或q节点
# left = self.lowestCommonAncestor(root.left, p, q)
# right = self.lowestCommonAncestor(root.right, p, q)
# # 四种情况
# # 1、如果当前这颗树的左右子树都找到了p或q 那么这个root节点就是它们的最近公共祖先
# #（因为是从下往上遍历的 所以出现的第一个祖先就是最近祖先）
# # 2、左子树没找到 右子树找到了p或q 直接返回右子树
# # 3、左子树找到了p或q 右子树没找到 直接返回左子树
# # 4、左子树没找到 右子树也没找到 返回None（这种情况其实不可能）
# if left and right: return root
# return left or right
# 方法2、先保存p、q的路径 再选出路径中的公共节点 最后一个公共节点即为最近公共节点
def dfs_pre(node, path, targt, res):
if not node: return
if node == targt:
path.append(node)
res.extend(path)
return
dfs_pre(node.left, path + [node], targt, res)
dfs_pre(node.right, path + [node], targt, res)
path_p, path_q = [], []
lowest = root
dfs_pre(root, [], p, path_p)
dfs_pre(root, [], q, path_q)
for u, v in zip(path_p, path_q):
if u == v:
lowest = u
# for u in path_p:
# for v in path_q:
# if u == v:
# lowest = v
return lowest
四、层次遍历
4.0、层次框架模板
leetcode102. 二叉树的层序遍历
一层一层输出：[ [3]，[9，20]，[15，7] ]
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, queue = [], [root]
while queue:
# 统计每一层的个数
arr, size = [], len(queue)
# 遍历这一层的所有节点 -> arr
while size:
cur = queue.pop(0)
arr.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
# 将该层所有节点加入res
res.append(arr)
return res
简化版输出输出：[3，9，20，15，7]
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
res, queue = [], [root]
while queue:
cur = queue.pop(0)
res.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res
4.1、经典题目
leetcode107. 二叉树的层序遍历 II
# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, queue = [], [root]
while queue:
arr, size = [], len(queue)
while size:
cur = queue.pop(0)
arr.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
res.append(arr)
# 直接翻转list
return res[::-1]
leetcode103. 二叉树的锯齿形层序遍历
# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue, res = [root], []
# 记录当前层的序号
level = 1
while queue:
size, arr = len(queue), []
while size:
cur = queue.pop(0)
arr.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
# 如果当前层序号为偶数，那么就将该层的节点全部翻转
if level % 2 == 0:
arr = arr[::-1]
res.append(arr)
level += 1
return res
leetcode513. 找树左下角的值
513. 找树左下角的值：层次 / 前序
# 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 findBottomLeftValue(self, root: TreeNode) -> int:
# 1、层次遍历
queue = [root]
res = root.val
while queue:
# 计算当前层的节点个数
size = len(queue)
# 遍历每一层的所有节点
for i in range(size):
cur = queue.pop(0)
# i==0: 每一层的第一个节点
if i == 0: res = cur.val
# 将左右节点加入queue中
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return res
# 2、前序遍历
maxDepth, mostLeft = 0, root.val
def dfs(node, curDepth):
# cur_depth来记录叶子节点所在的层数
nonlocal maxDepth, mostLeft
# 碰到空节点，递归结束
if not node: return
# 找到叶子节点且当前深度大于最大深度，更新maxDepth和mostLeft
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
mostLeft = node.val
# 递归调用左右子树 深度+1
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
dfs(root, 0)
return mostLeft
leetcode104. 二叉树的最大深度
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: TreeNode) -> int:
# 1、层次遍历
if not root: return 0
queue = [root]
depth = 0
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
depth += 1
return depth
# 2、先序遍历
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
dfs(root, 1)
return maxDepth
# 3、中序遍历
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
dfs(node.left, curDepth + 1)
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(node.right, curDepth + 1)
dfs(root, 1)
return maxDepth
# 4.1、后序遍历1
if not root: return 0
maxDepth = 1
def dfs(node, curDepth):
nonlocal maxDepth
if not node: return
dfs(node.left, curDepth + 1)
dfs(node.right, curDepth + 1)
# 每碰到一个叶子节点 且当前叶子节点所在分支的大小大于maxDepth，就更新当前这棵树的最大深度
if not node.left and not node.right and curDepth > maxDepth:
maxDepth = curDepth
dfs(root, 1)
return maxDepth
# 4.2、后序遍历2
def dfs(node):
if not node: return 0
leftD = dfs(node.left)
rightD = dfs(node.right)
return max(leftD, rightD) + 1
return dfs(root)
leetcode111. 二叉树的最小深度
# 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 minDepth(self, root: TreeNode) -> int:
if not root: return 0
queue = [root]
depth = 1
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
# 一旦哪一层发现了第一个叶节点 直接返回深度
# 因为是从上到下逐层遍历，所以发现的第一个叶子节点就是我们要求的最小深度
if not cur.left and not cur.right:
return depth
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
depth += 1
leetcode515. 在每个树行中找最大值
# 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 largestValues(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], [root]
while queue:
size, levelMax = len(queue), float('-inf')
while size:
cur = queue.pop(0)
# 比较得到每一层的最大值
if cur.val > levelMax:
levelMax = cur.val
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
res.append(levelMax)
return res
leetcode199. 二叉树的右视图
# 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 rightSideView(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], [root]
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
# 找到每一行的最后一个元素
if size == 1:
res.append(cur.val)
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
return res
leetcode637. 二叉树的层平均值
# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
if not root: return []
res, queue = [], [root]
while queue:
size, sumValue = len(queue), 0
count = size
while size:
cur = queue.pop(0)
# 统计当前层的所有节点的val和
sumValue += cur.val
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
# 求当前层的平均val
res.append(sumValue / count)
return res
leetcode429. N 叉树的层序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root: return []
res, queue = [], [root]
while queue:
size, arr = len(queue), []
while size:
cur = queue.pop(0)
arr.append(cur.val)
# 不是root.left和root.right入队了， 而是遍历root.children, 把各个节点入队
for c in cur.children:
queue.append(c)
size -= 1
res.append(arr)
return res
leetcode226. 翻转二叉树
# 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 invertTree(self, root: TreeNode) -> TreeNode:
# 1、前序遍历
def dfs(node):
# 空节点，递归结束
if not node: return
# 不是空节点（左右子树都不为空/左子树不为空+右子树为空/左子树为空+右子树不为空），就调换左右子树
node.left, node.right = node.right, node.left
# 递归调用左右子树
dfs(node.left)
dfs(node.right)
dfs(root)
return root
# 2、层次遍历
if not root: return None
queue = [root]
while queue:
cur = queue.pop(0)
cur.left, cur.right = cur.right, cur.left
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
return root
leetcode剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树: 递归 / 层次
这道题的层次遍历的框架和以往的题目有一点的差别，不是很大，要注意一下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
# 1、递归
# 判断A、B两棵子树是否为镜像(对称)
def isMirror(A, B):
if not A and not B: return True
if not A or not B: return False
if A.val != B.val: return False
return isMirror(A.left, B.right) and isMirror(A.right, B.left)
return isMirror(root.left, root.right) if root else True
# 2、层次
queue = [root]
while queue:
size, arr = len(queue), []
count = size
while size:
cur = queue.pop(0)
if cur:
arr.append(cur.val)
else:
arr.append('#')
if cur:
queue.append(cur.left)
queue.append(cur.right)
size -= 1
for i in range(count // 2):
if arr[i] != arr[~i]:
return False
return True
leetcode958. 二叉树的完全性检验（判断一颗二叉树是否是完全二叉树）
958. 二叉树的完全性检验（判断一颗二叉树是否是完全二叉树）
# 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 isCompleteTree(self, root: TreeNode) -> bool:
queue = [root]
while queue:
cur = queue.pop(0)
# 只要碰到一个None 就直接停止压入队列
if not cur:
break
queue.append(cur.left)
queue.append(cur.right)
# 再判断此时队列中是否还存在非None节点 如果还存在说明不是完全二叉树
for q in queue:
if q: return False
return True
leetcode116. 填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针：层次 / 穿针引线(很精彩的方法)
"""
# 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':
# 1、层次遍历
if not root: return None
queue = [root]
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
# 遍历每一层 将前size-1个元素的next指向queue[0](当前层当前元素的下一个元素)
# 最后一个节点不用管 因为初始状态下所有next指针都被设置为NULL
if size > 1:
cur.next = queue[0]
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
return root
# 2、穿针引线
if not root: return None
# 当前层链表
leftMost = root
while leftMost.left:
head = leftMost
# 遍历当前层链表
while head:
# 某个节点的左右子树连接
head.left.next = head.right
# 相邻节点AB A的右子树和B的左子树相连
# 初始状态下 所有 next 指针都被设置为NULL 所以每一层的最后一个节点可以不连接
if head.next:
head.right.next = head.next.left
head = head.next
leftMost = leftMost.left
return root
leetcode117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II：层次 / 穿针引线（很重要 暂时没弄很懂）
这两道题如果用层次遍历解决的话，其实是一样的。但是用穿针引线的话，这道题有点难度，不知道怎么找到每层的最左边元素，因为这个二叉树不是完全二叉树，不好找。
"""
"""
# 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':
# 1、层次遍历
if not root: return None
queue = [root]
while queue:
size = len(queue)
while size:
cur = queue.pop(0)
cur.next = queue[0] if size > 1 else None
if cur.left: queue.append(cur.left)
if cur.right: queue.append(cur.right)
size -= 1
return root
# 2、穿针引线
if not root: return None
mostLeft = root
while mostLeft: # 从每一层最左节点开始遍历每一层
dummyHead = Node(None) # 为下一行创建一个虚拟头节点，相当于下一行所有节点链表的头结点(每一层都会创建)
tail = dummyHead # 为下一行维护一个尾节点指针（初始化是虚拟节点）
cur = mostLeft
while cur: # 遍历当前层的节点
# 链接下一行的节点
if cur.left:
tail.next = cur.left
tail = tail.next
if cur.right:
tail.next = cur.right
tail = tail.next
cur = cur.next # cur同层移动到下一节点
mostLeft = dummyHead.next # 此处为换行操作，更新到下一行（这一步最重要）
return root
总结
先序遍历题目汇总
- 144. 二叉树的前序遍历??????????
- 257. 二叉树的所有路径
- 226. 翻转二叉树（求一颗二叉树的翻转/镜像/对称二叉树） = 剑指 Offer 27. 二叉树的镜像??????????
- 129. 求根节点到叶节点数字之和
- 404. 左叶子之和
- 513. 找树左下角的值
- 112. 路径总和??????
- 113. 路径总和 II??????
- 437. 路径总和 III??????
中序遍历题目汇总
- 94. 二叉树的中序遍历??????????
- 98. 验证二叉搜索树????
- 230. 二叉搜索树中第K小的元素
- 剑指 Offer 54. 二叉搜索树的第k大节点????
- 530. 二叉搜索树的最小绝对差
- 501. 二叉搜索树中的众数??????
- 538. 把二叉搜索树转换为累加树????
- 剑指 Offer 36. 二叉搜索树与双向链表 = 426. 将二叉搜索树转化为排序的双向链表（重要）????????
后序遍历题目汇总
- 145. 二叉树的后序遍历??????????
- 226. 翻转二叉树??????????
- 104. 二叉树的最大深度????????
- 559. N 叉树的最大深度
- 111. 二叉树的最小深度????????
- 543. 二叉树的直径 （重要）??????????
- 124. 二叉树中的最大路径和（重要）????????
- 222. 完全二叉树的节点个数
- 814. 二叉树剪枝
- 110. 判断是否平衡二叉树（重要 经典）??????????
- 236. 二叉树的最近公共祖先（很重要 难点 经典）??????????
层次遍历题目汇总
- 102. 二叉树的层序遍历??????????
- 107. 二叉树的层序遍历 II
- 103. 二叉树的锯齿形层序遍历??
- 513. 找树左下角的值
- 104. 二叉树的最大深度
- 111. 二叉树的最小深度
- 515. 在每个树行中找最大值
- 199. 二叉树的右视图????????
- 637. 二叉树的层平均值
- 429. N 叉树的层序遍历
- 226. 翻转二叉树 ??????????
- 剑指 Offer 28. 对称的二叉树(判断一颗树是否是对称二叉树)
- 958. 二叉树的完全性检验（判断一颗二叉树是否是完全二叉树）
- 116. 填充每个节点的下一个右侧节点指针
- 117. 填充每个节点的下一个右侧节点指针 II