空压机网站开发公司,网站建设使用的什么软件有哪些方面,电子商务网站建设收获,wordpress蜘蛛爬虫记录Python蓝桥杯训练#xff1a;基本数据结构 [二叉树] 上 文章目录Python蓝桥杯训练#xff1a;基本数据结构 [二叉树] 上一、前言二、有关二叉树理论基础1、二叉树的基本定义2、二叉树的常见类型3、二叉树的遍历方式三、有关二叉树的层序遍历的题目1、[二叉树的层序遍历](http…Python蓝桥杯训练基本数据结构 [二叉树] 上 文章目录Python蓝桥杯训练基本数据结构 [二叉树] 上一、前言二、有关二叉树理论基础1、二叉树的基本定义2、二叉树的常见类型3、二叉树的遍历方式三、有关二叉树的层序遍历的题目1、[二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)2、[N叉树的层序遍历](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/)3、填充每个节点的下一个右侧节点指针一、前言
目前蓝桥杯训练刷题刷到了二叉树中间的栈和队列我没有更新时间有点不太够但是我又觉得如果刷题不写笔记的话感觉等于没刷所以我还是将我刷题的过程以笔记的形式总结出来内容可能没有之前几次的丰富但是我还是会将重要的内容总结出来理论部分会有所减少我会更加专注 于总结刷题过程中的思考。
二、有关二叉树理论基础
二叉树是一种树状数据结构它的每个节点最多只有两个子节点。其中一个被称为左子节点另一个被称为右子节点。以下是有关二叉树的理论基础的详细总结
1、二叉树的基本定义
节点Node二叉树的基本单位它包含一个值Value和两个指针Pointer分别指向左子节点和右子节点如果没有子节点则指向 null 或空。根节点Root二叉树中的第一个节点它没有父节点是整棵树的起点。叶节点Leaf没有子节点的节点称为叶节点。内部节点Internal Node除了叶节点以外的节点都称为内部节点。高度Height二叉树的高度是从根节点到最深叶节点的最长路径的长度。空树的高度为0只有一个节点的二叉树的高度为1。深度Depth节点的深度是从根节点到该节点的唯一路径的长度。根节点的深度为0。路径Path是指从一个节点到另一个节点经过的所有节点的序列。子树Subtree是指由一个节点及其所有后代节点组成的二叉树。
2、二叉树的常见类型
普通二叉树Binary Tree每个节点最多只有两个子节点。完全二叉树Complete Binary Tree除了最后一层每一层的节点数都是满的并且最后一层的节点都尽可能地靠左。满二叉树Full Binary Tree每个节点都有 0 或 2 个子节点没有只有一个子节点的节点。二叉搜索树Binary Search Tree每个节点的左子树中的所有节点的值都小于该节点的值右子树中的所有节点的值都大于该节点的值。平衡二叉树Balanced Binary Tree左右子树的高度差不超过 1 的二叉树。
3、二叉树的遍历方式
二叉树的深度优先遍历方式有三种前序遍历、中序遍历和后序遍历广度优先遍历有层序遍历。这些遍历方式都是基于递归的它们都可以使用递归或迭代法来实现。 深度优先遍历 前序遍历先访问根节点再递归地访问左子树和右子树。 class Node:def __init__(self, value):self.left Noneself.right Noneself.value valuedef preorder_traversal(node):if node is None:returnprint(node.value)preorder_traversal(node.left)preorder_traversal(node.right)root Node(1)
root.left Node(2)
root.right Node(3)
root.left.left Node(4)
root.left.right Node(5)print(前序遍历结果)
preorder_traversal(root)前序遍历结果
1
2
4
5
3中序遍历先递归地访问左子树再访问根节点最后递归地访问右子树。 class Node:def __init__(self, value):self.left Noneself.right Noneself.value valuedef inorder_traversal(node):if node is None:returninorder_traversal(node.left)print(node.value)inorder_traversal(node.right)root Node(1)
root.left Node(2)
root.right Node(3)
root.left.left Node(4)
root.left.right Node(5)print(中序遍历结果)
inorder_traversal(root)中序遍历结果
4
2
5
1
3后序遍历先递归地访问左子树和右子树最后访问根节点。 class Node:def __init__(self, value):self.left Noneself.right Noneself.value valuedef postorder_traversal(node):if node is None:returnpostorder_traversal(node.left)postorder_traversal(node.right)print(node.value)root Node(1)
root.left Node(2)
root.right Node(3)
root.left.left Node(4)
root.left.right Node(5)print(后序遍历结果)
postorder_traversal(root)后序遍历结果
4
5
2
3
1广度优先遍历 也称作层序遍历是按照层次顺序从上往下、从左往右遍历树的节点。广度优先遍历需要借助队列来实现每次从队列中取出一个节点访问它的左右子节点将子节点依次加入队列中直到队列为空。 from collections import dequeclass Node:def __init__(self, value):self.left Noneself.right Noneself.value valuedef breadth_first_traversal(node):if node is None:returnqueue deque()queue.append(node)while queue:current_node queue.popleft()print(current_node.value)if current_node.left:queue.append(current_node.left)if current_node.right:queue.append(current_node.right)root Node(1)
root.left Node(2)
root.right Node(3)
root.left.left Node(4)
root.left.right Node(5)print(广度优先遍历结果)
breadth_first_traversal(root)广度优先遍历结果
1
2
3
4
5三、有关二叉树的层序遍历的题目
二叉树的层序遍历相比于其深度优先遍历会简单很多基本记住一个模板很多题目就可以直接套用。
1、二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[]提示 树中节点数目在范围 [0, 2000] 内 -1000 Node.val 1000
这道题就是考察我们对二叉树层序遍历的掌握情况在上面的二叉树理论基础中的广度优先遍历中我们已经实现了这个过程并且使用的迭代方法下面我来说一下递归的方法如何实现。
实现思路跟迭代法一样就是代码更加简洁具体思路我写在了代码注释里面。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution():def levelOrder(self, root: TreeNode) - List[List[int]]:result [] # 定义一个列表用于保存最终结果def traverse(node, level):if not node: # 如果当前节点为空直接返回returnif level len(result): # 如果 result 中不存在当前层的列表创建一个新的列表result.append([])result[level].append(node.val) # 将当前节点的值加入当前层的列表中traverse(node.left, level 1) # 6递归遍历当前节点的左子树traverse(node.right, level 1) # 7. 递归遍历当前节点的右子树traverse(root, 0) # 开始遍历二叉树return result # 返回最终结果2、N叉树的层序遍历
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。
示例 1
输入root [1,null,3,2,4,null,5,6]
输出[[1],[3,2,4],[5,6]]示例 2 输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示
树的高度不会超过 1000树的节点总数在 [0, 10^4] 之间
这道题目也是套模板只不过在左孩子和右孩子的基础上多了一个孩子。 # Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children children# 迭代法
class Solution:def levelOrder(self, root: Node) - List[List[int]]:if not root:return []res []queue [root]while queue:level []size len(queue)for i in range(size):node queue.pop(0)level.append(node.val)for child in node.children:queue.append(child)res.append(level)return res
递归法实现就是从根节点开始递归遍历每一层的节点并将它们添加到对应层的列表中。
class Solution:def levelOrder(self, root: Node) - List[List[int]]:if not root: # 如果根节点为空则直接返回空列表return []res [] # 存储结果的列表def traverse(node, level):# 如果当前层数等于列表长度则向列表中添加一个新列表if len(res) level:res.append([])# 将当前节点的值加入到对应层的列表中res[level].append(node.val)# 递归遍历当前节点的所有子节点并将它们的层数加一作为递归函数的参数进行递归for child in node.children:traverse(child, level1)# 从根节点开始递归遍历traverse(root, 0)return res # 返回结果列表3、填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。
示例 1 输入root [1,2,3,4,5,6,7]
输出[1,#,2,3,#,4,5,6,7,#]
解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化的输出按层序遍历排列同一层节点由 next 指针连接# 标志着每一层的结束。示例 2:
输入root []
输出[]提示
树中节点的数量在 [0, 212 - 1] 范围内-1000 node.val 1000
进阶
你只能使用常量级额外空间。使用递归解题也符合要求本题中递归程序占用的栈空间不算做额外的空间复杂度。
这道题目的要求就是给定一棵二叉树将每个节点的右子节点指向其在右边的下一个节点如果右边没有节点则将其指向None。要求使用常数级额外空间也就是说不可以使用队列等数据结构。
题目要求在不使用队列等数据结构的情况下将每个节点的右子节点指向其在右边的下一个节点。
我们可以从根节点开始对于每一层节点依次更新它们的右子节点直到该层节点的最后一个节点。然后再进入下一层节点进行同样的操作。
具体来说我们指定一个指针 cur表示当前层节点的最左边的节点初始时 cur 指向根节点。在每一层的循环中我们从左到右遍历该层的所有节点对于每个节点先将其左子节点的 next 指针指向其右子节点再将其右子节点的 next 指针指向其 next 指针所指向节点的左子节点如果该节点的 next 指针所指向节点不存在则将其右子节点的 next 指针指向 None。然后将该节点移动到下一个节点直到该层的所有节点都被更新为止。最后将 cur 指针移动到下一层的最左边的节点并重复上述操作直到遍历完所有层为止。 # 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: Node) - Node:if not root:return Nonecur rootwhile cur.left:node curwhile node:node.left.next node.rightif node.next:node.right.next node.next.leftnode node.nextcur cur.leftreturn root时间复杂度O(n)O(n)O(n)其中 nnn 是二叉树中的节点个数。
空间复杂度O(1)O(1)O(1)。除了存储答案所需的空间外我们只需要维护常数个变量因此空间复杂度是 O(1)O(1)O(1)。
