目录
前言
上文带大家学习了二叉树的理论基础，如果没看过的点这去回顾下 ，今天带大家进行二叉树的实战篇1，学会如何去遍历二叉树，无论什么要求怎么遍历，一文带大家弄懂。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！
二叉树的递归遍历
说到二叉树的递归遍历，这里正好带大家巩固下遍历的知识。很多人可能对于到递归就是一听就会，一写就废的。那么为什么这样呢？因为递归就是将复杂问题化为简单的重复的小问题，一听上去好像我们会了，真的写起来却发现自己写不出来，这就是递归三要素没有彻底的搞清楚。什么是递归三要素：
- 确定递归的参数和返回值：我们我们递归需要传递进什么参数去继续处理，并且还要确定函数的返回值是什么，进而确定函数的返回类型。
- 确定递归的终止条件：这是很重要的，我们什么时候递归终止可以不用在递归了，否则就将会陷入递归无限的死循环中。这会导致系统的栈溢出情况。
- 确定单层递归的逻辑：确定每一层递归我们需要处理什么内容，同时在这也会重复调用自己来实现递归过程。
那么我们就以二叉树的递归遍历来联手
前序遍历
再次回顾下，前序遍历的顺序是根左右，先根节点，在左右节点。所以就很直观了，我们先保存根节点值，在进入左子树保存，直至节点为空结束递归。后面的中序遍历和后序遍历是同样的道理，就不再叙述了，直接放代码。
# 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: TreeNode) -> List[int]: res = [] def dfs(node): if node is None: return res.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return res 中序遍历
class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] def dfs(node): if node is None: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return res 后续遍历
class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = [] def dfs(node): if node is None: return dfs(node.left) dfs(node.right) res.append(node.val) dfs(root) return res 二叉树的迭代遍历
二叉树的递归遍历代码很简单，也很容易去理解的，那么我们再来看看，若是不用递归的方式去前中后序遍历该怎么去进行，这就是这节要说的二叉树的迭代遍历。
前序遍历
我们来看前序遍历的顺序是根左右，那么我们通过栈来进行操作，先根节点进栈，然后根节点出栈，然后重点来了，先进右节点在进左节点。为什么要这样？因为我们顺序是根左右，栈的特性后进先出，那么就要右节点先进栈，左节点在进栈，然后在以进栈的左节点作为根节点重复上述操作，直到将栈清空为止。实现代码为：
class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: # 根节点为空则返回空列表 if not root: return [] stack = [root] result = [] while stack: node = stack.pop() # 中节点先处理 result.append(node.val) # 右孩子先入栈 if node.right: stack.append(node.right) # 左孩子后入栈 if node.left: stack.append(node.left) return result 中序遍历
刚才讲了前序遍历的迭代法，那么我们是否可以以相同的方式来进行呢？当然不行？我们来看为什么，是因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么中序遍历就是先从根节点开始进栈，往左节点一直进栈，直至为空，然后弹出其栈顶的节点返回，再看其有没有右节点有就继续进栈，在左节点遍历直至空，重复操作即可。
class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] stack = [] # 不能提前将root节点加入stack中 result = [] cur = root while cur or stack: # 先迭代访问最底层的左子树节点 if cur: stack.append(cur) cur = cur.left # 到达最左节点后处理栈顶节点 else: cur = stack.pop() result.append(cur.val) # 取栈顶元素右节点 cur = cur.right return result 后序遍历
后序遍历就比较简单了，我们可以参考前序遍历，前序遍历的顺序是根左右，后序遍历的顺序是左右根，那我们可以按照前序遍历的方法，不过换一下先进左节点在进右节点，就可以得到根右左的顺序，我们再将他倒序即可得到左右根。
class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] stack = [root] result = [] while stack: node = stack.pop() # 中节点先处理 result.append(node.val) # 左孩子先入栈 if node.left: stack.append(node.left) # 右孩子后入栈 if node.right: stack.append(node.right) # 将最终的数组翻转 return result[::-1] 二叉树的层序遍历
层序遍历(学会这个，以一打十)
相关技巧：层序遍历就是一层的所有节点进行输出，我们可以借助队列来实现，根节点进入队列，其子节点进入队列，然后根节点出队列记录。我们这里可以借助一个变量level来记录其所属的不同层。所以其实现代码如下：
# 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: Optional[TreeNode]) -> List[List[int]]: if not root: return [] queue = collections.deque([root]) result = [] while queue: level = [] for _ in range(len(queue)): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) result.append(level) return result 层序遍历(倒序)
107. 二叉树的层序遍历 II - 力扣（LeetCode）
直接按照层序遍历的结果倒序即可，非常简单。
# 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 [] queue = collections.deque([root]) result = [] while queue: level = [] for _ in range(len(queue)): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) result.append(level) return result[::-1] 二叉树的右视图
层序遍历，每次输出每层的最后一个节点就行了。
# 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: Optional[TreeNode]) -> List[int]: if not root: return [] queue=collections.deque([root]) right_view=[] while queue: levels=len(queue) for i in range(levels): node=queue.popleft() if i == levels-1: right_view.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return right_view 二叉树的层平均值
每层求和求平均即可
# 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: TreeNode) -> List[float]: if not root: return [] queue = collections.deque([root]) averages = [] while queue: size = len(queue) level_sum = 0 for i in range(size): node = queue.popleft() level_sum += node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) averages.append(level_sum / size) return averages N叉树的层序遍历
""" # Definition for a Node. class Node: def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None): self.val = val self.children = children """ class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: if not root: return [] result = [] queue = collections.deque([root]) while queue: level_size = len(queue) level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) for child in node.children: queue.append(child) result.append(level) return result 在每行中找出最大值
515. 在每个树行中找最大值 - 力扣（LeetCode）
在每层找最大值，作比较记录即可
# 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 [] result = [] queue = collections.deque([root]) while queue: level_size = len(queue) max_val = float('-inf') for _ in range(level_size): node = queue.popleft() max_val = max(max_val, node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(max_val) return result 填充每个节点的下一个右侧节点指针
通过层序遍历，然后每层内指向下个节点即可，这里需要个额外的指针记录上个节点
""" # 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 = collections.deque([root]) while queue: level_size = len(queue) prev = None for i in range(level_size): node = queue.popleft() if prev: prev.next = node prev = node if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）
这里的不同就是上个满二叉树，这里并不是满二叉树，不过原理逻辑相同。
""" # 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 = collections.deque([root]) while queue: level_size = len(queue) prev = None for i in range(level_size): node = queue.popleft() if prev: prev.next = node prev = node if node.left: queue.append(node.left) if node.right: queue.append(node.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 maxDepth(self, root: TreeNode) -> int: if not root: return 0 depth = 0 queue = collections.deque([root]) while queue: depth += 1 for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return 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: def minDepth(self, root: TreeNode) -> int: if not root: return 0 depth = 0 queue = collections.deque([root]) while queue: depth += 1 for _ in range(len(queue)): node = queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth 算法基础系列
一文了解什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇
【双指针法】:这么常用的你怎么能不知道 - carpell - 博客园
【二叉树】理论基础篇1 - carpell - 博客园
吐血整理 Bolt.diy 部署与应用攻略