登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›二叉树实战篇1

二叉树实战篇1

庞环 5 天前
目录

  • 前言
  • 二叉树的递归遍历

    • 前序遍历
    • 中序遍历
    • 后续遍历

  • 二叉树的迭代遍历

    • 前序遍历
    • 中序遍历
    • 后序遍历

  • 二叉树的层序遍历

    • 层序遍历(学会这个，以一打十)
    • 层序遍历(倒序)
    • 二叉树的右视图
    • 二叉树的层平均值
    • N叉树的层序遍历
    • 在每行中找出最大值
    • 填充每个节点的下一个右侧节点指针
    • 填充每个节点的下一个右侧节点指针 II
    • 二叉树的最大深度
    • 二叉树的最小深度

  • 算法基础系列

前言

上文带大家学习了二叉树的理论基础，如果没看过的点这去回顾下   ，今天带大家进行二叉树的实战篇1，学会如何去遍历二叉树，无论什么要求怎么遍历，一文带大家弄懂。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！
1.png

二叉树的递归遍历

说到二叉树的递归遍历，这里正好带大家巩固下遍历的知识。很多人可能对于到递归就是一听就会，一写就废的。那么为什么这样呢？因为递归就是将复杂问题化为简单的重复的小问题，一听上去好像我们会了，真的写起来却发现自己写不出来，这就是递归三要素没有彻底的搞清楚。什么是递归三要素：

  • 确定递归的参数和返回值：我们我们递归需要传递进什么参数去继续处理，并且还要确定函数的返回值是什么，进而确定函数的返回类型。
  • 确定递归的终止条件：这是很重要的，我们什么时候递归终止可以不用在递归了，否则就将会陷入递归无限的死循环中。这会导致系统的栈溢出情况。
  • 确定单层递归的逻辑：确定每一层递归我们需要处理什么内容，同时在这也会重复调用自己来实现递归过程。
那么我们就以二叉树的递归遍历来联手
前序遍历

再次回顾下，前序遍历的顺序是根左右，先根节点，在左右节点。所以就很直观了，我们先保存根节点值，在进入左子树保存，直至节点为空结束递归。后面的中序遍历和后序遍历是同样的道理，就不再叙述了，直接放代码。
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  8. class Solution:
  9.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  10.         res = []
  11.         
  12.         def dfs(node):
  13.             if node is None:
  14.                 return
  15.             
  16.             res.append(node.val)
  17.             dfs(node.left)
  18.             dfs(node.right)
  19.         dfs(root)
  20.         return res
复制代码
中序遍历
  1. class Solution:
  2.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  3.         res = []
  4.         
  5.         def dfs(node):
  6.             if node is None:
  7.                 return
  8.             
  9.             dfs(node.left)
  10.             res.append(node.val)
  11.             dfs(node.right)
  12.         dfs(root)
  13.         return res
复制代码
后续遍历
  1. class Solution:
  2.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  3.         res = []
  4.         
  5.         def dfs(node):
  6.             if node is None:
  7.                 return
  8.             
  9.             dfs(node.left)
  10.             dfs(node.right)
  11.             res.append(node.val)
  13.         dfs(root)
  14.         return res
复制代码
二叉树的迭代遍历

二叉树的递归遍历代码很简单，也很容易去理解的，那么我们再来看看，若是不用递归的方式去前中后序遍历该怎么去进行，这就是这节要说的二叉树的迭代遍历。
前序遍历

我们来看前序遍历的顺序是根左右，那么我们通过栈来进行操作，先根节点进栈，然后根节点出栈，然后重点来了，先进右节点在进左节点。为什么要这样？因为我们顺序是根左右，栈的特性后进先出，那么就要右节点先进栈，左节点在进栈，然后在以进栈的左节点作为根节点重复上述操作，直到将栈清空为止。实现代码为：
  1. class Solution:
  2.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  3.         # 根节点为空则返回空列表
  4.         if not root:
  5.             return []
  6.         stack = [root]
  7.         result = []
  8.         while stack:
  9.             node = stack.pop()
  10.             # 中节点先处理
  11.             result.append(node.val)
  12.             # 右孩子先入栈
  13.             if node.right:
  14.                 stack.append(node.right)
  15.             # 左孩子后入栈
  16.             if node.left:
  17.                 stack.append(node.left)
  18.         return result
复制代码
中序遍历

刚才讲了前序遍历的迭代法，那么我们是否可以以相同的方式来进行呢？当然不行？我们来看为什么，是因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么中序遍历就是先从根节点开始进栈，往左节点一直进栈，直至为空，然后弹出其栈顶的节点返回，再看其有没有右节点有就继续进栈，在左节点遍历直至空，重复操作即可。
  1. class Solution:
  2.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  4.         if not root:
  5.             return []
  6.         stack = []  # 不能提前将root节点加入stack中
  8.         result = []
  9.         cur = root
  10.         while cur or stack:
  11.             # 先迭代访问最底层的左子树节点
  12.             if cur:     
  13.                 stack.append(cur)
  14.                 cur = cur.left               
  15.             # 到达最左节点后处理栈顶节点   
  16.             else:               
  17.                 cur = stack.pop()
  18.                 result.append(cur.val)
  19.                 # 取栈顶元素右节点
  20.                 cur = cur.right       
  21.         return result
复制代码
后序遍历

后序遍历就比较简单了，我们可以参考前序遍历，前序遍历的顺序是根左右，后序遍历的顺序是左右根，那我们可以按照前序遍历的方法，不过换一下先进左节点在进右节点，就可以得到根右左的顺序，我们再将他倒序即可得到左右根。
  1. class Solution:
  2.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  3.         if not root:
  4.             return []
  5.         stack = [root]
  6.         result = []
  7.         while stack:
  8.             node = stack.pop()
  9.             # 中节点先处理
  10.             result.append(node.val)
  11.             # 左孩子先入栈
  12.             if node.left:
  13.                 stack.append(node.left)
  14.             # 右孩子后入栈
  15.             if node.right:
  16.                 stack.append(node.right)
  17.         # 将最终的数组翻转
  18.         return result[::-1]
复制代码
二叉树的层序遍历

层序遍历(学会这个，以一打十)

102. 二叉树的层序遍历 - 力扣（LeetCode）
2.png

相关技巧：层序遍历就是一层的所有节点进行输出，我们可以借助队列来实现，根节点进入队列，其子节点进入队列，然后根节点出队列记录。我们这里可以借助一个变量level来记录其所属的不同层。所以其实现代码如下：
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
  9.         if not root:
  10.             return []
  11.         queue = collections.deque([root])
  12.         result = []
  13.         while queue:
  14.             level = []
  15.             for _ in range(len(queue)):
  16.                 cur = queue.popleft()
  17.                 level.append(cur.val)
  18.                 if cur.left:
  19.                     queue.append(cur.left)
  20.                 if cur.right:
  21.                     queue.append(cur.right)
  22.             result.append(level)
  23.         return result
复制代码
层序遍历(倒序)

107. 二叉树的层序遍历 II - 力扣（LeetCode）
直接按照层序遍历的结果倒序即可，非常简单。
3.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
  9.         if not root:
  10.             return []
  11.         queue = collections.deque([root])
  12.         result = []
  13.         while queue:
  14.             level = []
  15.             for _ in range(len(queue)):
  16.                 cur = queue.popleft()
  17.                 level.append(cur.val)
  18.                 if cur.left:
  19.                     queue.append(cur.left)
  20.                 if cur.right:
  21.                     queue.append(cur.right)
  22.             result.append(level)
  23.         return result[::-1]
复制代码
二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）
层序遍历，每次输出每层的最后一个节点就行了。
4.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
  9.         if not root:
  10.             return []
  11.         
  12.         queue=collections.deque([root])
  13.         right_view=[]
  14.         while queue:
  15.             levels=len(queue)
  16.             for i in range(levels):
  17.                 node=queue.popleft()
  19.                 if i == levels-1:
  20.                     right_view.append(node.val)
  22.                 if node.left:
  23.                     queue.append(node.left)
  24.                 if node.right:
  25.                     queue.append(node.right)
  26.         return right_view
复制代码
二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode）
每层求和求平均即可
5.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def averageOfLevels(self, root: TreeNode) -> List[float]:
  9.         if not root:
  10.             return []
  12.         queue = collections.deque([root])
  13.         averages = []
  14.         
  15.         while queue:
  16.             size = len(queue)
  17.             level_sum = 0
  18.             
  19.             for i in range(size):
  20.                 node = queue.popleft()
  21.                
  22.                
  23.                 level_sum += node.val
  24.                     
  25.                 if node.left:
  26.                     queue.append(node.left)
  27.                 if node.right:
  28.                     queue.append(node.right)
  29.             
  30.             averages.append(level_sum / size)
  31.         
  32.         return averages
复制代码
N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）
6.png
  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
  5.         self.val = val
  6.         self.children = children
  7. """
  9. class Solution:
  10.     def levelOrder(self, root: 'Node') -> List[List[int]]:
  11.         if not root:
  12.             return []
  14.         result = []
  15.         queue = collections.deque([root])
  17.         while queue:
  18.             level_size = len(queue)
  19.             level = []
  21.             for _ in range(level_size):
  22.                 node = queue.popleft()
  23.                 level.append(node.val)
  25.                 for child in node.children:
  26.                     queue.append(child)
  28.             result.append(level)
  30.         return result
复制代码
在每行中找出最大值

515. 在每个树行中找最大值 - 力扣（LeetCode）
在每层找最大值，作比较记录即可
7.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def largestValues(self, root: TreeNode) -> List[int]:
  9.         if not root:
  10.             return []
  12.         result = []
  13.         queue = collections.deque([root])
  15.         while queue:
  16.             level_size = len(queue)
  17.             max_val = float('-inf')
  19.             for _ in range(level_size):
  20.                 node = queue.popleft()
  21.                 max_val = max(max_val, node.val)
  23.                 if node.left:
  24.                     queue.append(node.left)
  26.                 if node.right:
  27.                     queue.append(node.right)
  29.             result.append(max_val)
  31.         return result
复制代码
填充每个节点的下一个右侧节点指针

通过层序遍历，然后每层内指向下个节点即可，这里需要个额外的指针记录上个节点
8.png
  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
  5.         self.val = val
  6.         self.left = left
  7.         self.right = right
  8.         self.next = next
  9. """
  11. class Solution:
  12.     def connect(self, root: 'Node') -> 'Node':
  13.         if not root:
  14.             return root
  15.         
  16.         queue = collections.deque([root])
  17.         
  18.         while queue:
  19.             level_size = len(queue)
  20.             prev = None
  21.             
  22.             for i in range(level_size):
  23.                 node = queue.popleft()
  24.                
  25.                 if prev:
  26.                     prev.next = node
  27.                
  28.                 prev = node
  29.                
  30.                 if node.left:
  31.                     queue.append(node.left)
  32.                
  33.                 if node.right:
  34.                     queue.append(node.right)
  35.         
  36.         return root
复制代码
填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）
这里的不同就是上个满二叉树，这里并不是满二叉树，不过原理逻辑相同。
9.png
  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
  5.         self.val = val
  6.         self.left = left
  7.         self.right = right
  8.         self.next = next
  9. """
  11. class Solution:
  12.     def connect(self, root: 'Node') -> 'Node':
  13.         if not root:
  14.             return root
  15.         
  16.         queue = collections.deque([root])
  17.         
  18.         while queue:
  19.             level_size = len(queue)
  20.             prev = None
  21.             
  22.             for i in range(level_size):
  23.                 node = queue.popleft()
  24.                
  25.                 if prev:
  26.                     prev.next = node
  27.                
  28.                 prev = node
  29.                
  30.                 if node.left:
  31.                     queue.append(node.left)
  32.                
  33.                 if node.right:
  34.                     queue.append(node.right)
  35.         
  36.         return root
复制代码
二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）
10.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def maxDepth(self, root: TreeNode) -> int:
  9.         if not root:
  10.             return 0
  11.         
  12.         depth = 0
  13.         queue = collections.deque([root])
  14.         
  15.         while queue:
  16.             depth += 1
  17.             for _ in range(len(queue)):
  18.                 node = queue.popleft()
  19.                 if node.left:
  20.                     queue.append(node.left)
  21.                 if node.right:
  22.                     queue.append(node.right)
  23.         
  24.         return depth
复制代码
二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）
11.png
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def minDepth(self, root: TreeNode) -> int:
  9.         if not root:
  10.             return 0
  11.         depth = 0
  12.         queue = collections.deque([root])
  13.         
  14.         while queue:
  15.             depth += 1
  16.             for _ in range(len(queue)):
  17.                 node = queue.popleft()
  18.                
  19.                 if not node.left and not node.right:
  20.                     return depth
  21.             
  22.                 if node.left:
  23.                     queue.append(node.left)
  24.                     
  25.                 if node.right:
  26.                     queue.append(node.right)
  28.         return depth
复制代码
算法基础系列

一文了解什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇
【双指针法】:这么常用的你怎么能不知道 - carpell - 博客园
【二叉树】理论基础篇1 - carpell - 博客园

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
庞环
5 天前

0

粉丝关注

11

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫