电商网站的建设与安全,gta5买房网站正在建设,电子商务网站建设与管理考卷,云服务器搭建wordpressPython蓝桥杯训练#xff1a;基本数据结构 [二叉树] 中 文章目录Python蓝桥杯训练#xff1a;基本数据结构 [二叉树] 中一、[翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/)二、[对称二叉树](https://leetcode.cn/problems/symmetric-tree/)三、[二叉树的最…Python蓝桥杯训练基本数据结构 [二叉树] 中 文章目录Python蓝桥杯训练基本数据结构 [二叉树] 中一、[翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/)二、[对称二叉树](https://leetcode.cn/problems/symmetric-tree/)三、[二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)四、[二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)五、[完全二叉树的节点个数](https://leetcode.cn/problems/count-complete-tree-nodes/)六、[平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/)一、翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例 1 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2 输入root [2,1,3]
输出[2,3,1]示例 3
输入root []
输出[]提示
树中节点数目范围在 [0, 100] 内-100 Node.val 100
这道题目要求我们翻转一棵二叉树可以使用递归的思路来解决问题。对于一个二叉树而言可以将它的左右子树看作两个独立的小问题因此可以先将左右子树分别翻转然后再将整个树进行翻转。
具体实现时可以编写一个递归函数对于每一个节点而言先分别翻转左右子树然后将左右子树交换即可。如果节点为空直接返回即可。
class Solution:def invertTree(self, root: TreeNode) - TreeNode:if not root:return None# 递归翻转左右子树left self.invertTree(root.left)right self.invertTree(root.right)# 交换左右子树root.left rightroot.right leftreturn root上面算法我们使用的遍历顺序是后序遍历使用前序遍历也可以解决该算法的时间复杂度为 O(n)O(n)O(n)其中 nnn 是二叉树的节点个数因为每个节点都会被访问一次。空间复杂度为 O(n)O(n)O(n)因为递归函数会使用系统栈最坏情况下系统栈的深度等于二叉树的高度即为 O(n)O(n)O(n)。
二、对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100
**进阶**你可以运用递归和迭代两种方法解决这个问题吗
首先可以通过递归的方法来判断一棵二叉树是否是镜像对称的。对于一棵二叉树而言如果它是镜像对称的那么它的左右子树也是镜像对称的。因此可以编写一个递归函数来判断左右子树是否镜像对称然后判断根节点的左右子树是否镜像对称即可。
具体实现时可以编写一个递归函数 isMirror该函数接受两个参数 left 和 right分别表示两棵子树。如果两棵子树均为空返回 True如果其中一棵子树为空返回 False如果两棵子树的根节点的值不相等返回 False否则递归判断两棵子树的左右子树是否镜像对称。
class Solution(object):def isSymmetric(self, root):# 如果二叉树为空则直接返回 Trueif not root:return True# 如果二叉树不为空则递归判断其左右子树是否镜像对称return self.isMirror(root.left, root.right)def isMirror(self, left, right):# 如果两棵二叉树均为空则返回 Trueif not left and not right:return True# 如果其中一棵二叉树为空则返回 Falseif not left or not right:return False# 如果两棵二叉树的根节点的值不相等则返回 Falseif left.val ! right.val:return False# 递归判断两棵二叉树的左右子树是否镜像对称return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)三、二叉树的最大深度
给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3,9,20,null,null,15,7] 3/ \9 20/ \15 7返回它的最大深度 3 。
题目要求找出二叉树的最大深度因此可以通过深度优先搜索的方式而且推荐使用后序遍历来遍历二叉树记录每个节点的深度然后返回最大深度即可。
具体实现时可以编写一个递归函数 maxDepth该函数接受一个参数 node表示当前节点。如果当前节点为空则返回 0否则分别递归遍历当前节点的左右子树返回左右子树深度的较大值加上 1即为当前节点的深度。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def maxDepth(self, root):# 如果二叉树为空则返回 0if not root:return 0# 分别递归遍历当前节点的左右子树left_depth self.maxDepth(root.left)right_depth self.maxDepth(root.right)# 返回左右子树深度的较大值加上 1即为当前节点的深度return max(left_depth, right_depth) 1四、二叉树的最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明**叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5提示
树中节点数的范围在 [0, 105] 内-1000 Node.val 1000
题目要求找出二叉树的最小深度因此我妈可以通过深度优先搜索的方式来遍历二叉树记录每个节点的深度然后返回最小深度即可。
具体实现时可以编写一个递归函数 minDepth该函数接受一个参数 node表示当前节点。如果当前节点为空则返回 0否则分别递归遍历当前节点的左右子树如果当前节点有左右子树则返回左右子树深度的较小值加上 1否则返回左右子树深度的较大值加上 1即为当前节点的深度。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def minDepth(self, root):# 如果二叉树为空则返回 0if not root:return 0# 分别递归遍历当前节点的左右子树left_depth self.minDepth(root.left)right_depth self.minDepth(root.right)if not root.left or not root.right:# 如果当前节点只有一个子节点则返回另一个子树的深度加上 1return left_depth right_depth 1else:# 如果当前节点有左右子树则返回左右子树深度的较小值加上 1return min(left_depth, right_depth) 1这里需要注意的是在计算当前节点只有一个子节点的情况时我们需要将其另一个子树的深度加上 1因为当前节点不是叶子节点而是只有一个子节点的非叶子节点。
五、完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
示例 1 输入root [1,2,3,4,5,6]
输出6示例 2
输入root []
输出0示例 3
输入root [1]
输出1提示
树中节点的数目范围是[0, 5 * 104]0 Node.val 5 * 104题目数据保证输入的树是 完全二叉树
**进阶**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗
在这里我们可以直接当作普通二叉树来处理也就是之前练习的层序遍历直接使用那个模板记录遍历的节点数量就可以了。
在这里我们主要来着重利用完全二叉树的性质来解决问题由于完全二叉树的特殊性质我们可以先分别求出左子树和右子树的高度然后根据它们的高度分情况讨论。
如果左右子树的高度相同说明左子树是一棵满二叉树右子树是一棵完全二叉树那么左子树的节点个数可以直接计算右子树的节点个数可以递归地求解。如果左右子树的高度不同说明右子树是一棵满二叉树左子树是一棵完全二叉树那么右子树的节点个数可以直接计算左子树的节点个数可以递归地求解。
最终根据上述讨论的结果我们可以递归地求解出完全二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def countNodes(self, root):if not root:return 0# 分别求出左子树和右子树的高度left_height self.get_height(root.left)right_height self.get_height(root.right)# 如果左右子树的高度相同说明左子树是一棵满二叉树右子树是一棵完全二叉树if left_height right_height:# 左子树的节点个数可以直接计算return (1 left_height) self.countNodes(root.right)# 如果左右子树的高度不同说明右子树是一棵满二叉树左子树是一棵完全二叉树else:# 右子树的节点个数可以直接计算return (1 right_height) self.countNodes(root.left)def get_height(self, node):height 0while node:height 1node node.leftreturn height我们也可以换一个实现思路首先判断二叉树是否为空若为空则节点个数为0直接返回否则记录左子树和右子树的根节点同时记录左子树和右子树的深度初始值都为0。
接着通过循环不断地遍历左子树和右子树直到无法遍历统计出左子树和右子树的深度。
如果左子树的深度等于右子树的深度说明左子树是满二叉树右子树是完全二叉树此时可以利用满二叉树的节点数公式计算出总节点数即 2leftDepth1−12^{leftDepth1}-12leftDepth1−1其中 leftDepthleftDepthleftDepth 表示左子树的深度。
如果左子树的深度不等于右子树的深度说明左子树是完全二叉树右子树是满二叉树此时可以递归计算左子树和右子树的节点个数并将它们加起来再加上根节点即可得到总节点数。
最终返回计算出的节点数即可。
class Solution:def countNodes(self, root) - int:if not root:return 0left root.leftright root.rightleftDepth 0 #这里初始为0是有目的的为了下面求指数方便rightDepth 0while left: #求左子树深度left left.leftleftDepth 1while right: #求右子树深度right right.rightrightDepth 1if leftDepth rightDepth:return (2 leftDepth) - 1 #注意(21) 相当于2^2所以leftDepth初始为0return self.countNodes(root.left) self.countNodes(root.right) 1六、平衡二叉树
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1 输入root [3,9,20,null,null,15,7]
输出true示例 2 输入root [1,2,2,3,3,null,null,4,4]
输出false示例 3
输入root []
输出true提示
树中的节点数在范围 [0, 5000] 内-104 Node.val 104
首先我们需要思考的是对于一棵二叉树如果它是一棵空树则它是平衡二叉树因为它没有任何节点高度为0。
接着我们可以通过递归的方式判断以每个节点为根的子树是否是平衡二叉树。
对于每个节点我们需要计算它的左子树和右子树的高度并判断它们的高度差是否大于1如果大于1则说明该节点的子树不是平衡二叉树否则递归判断它的左子树和右子树是否是平衡二叉树如果左子树和右子树都是平衡二叉树则该节点的子树也是平衡二叉树。
最终如果整个二叉树是平衡二叉树则返回True否则返回False。
class Solution:def isBalanced(self, root) - bool:# 调用方法 getHeight 来获取二叉树的高度if self.getHeight(root) ! -1:return Trueelse:return Falsedef getHeight(self, root):# 如果当前节点是空节点则返回0if not root:return 0# 分别计算当前节点的左右子树的高度# 如果左右子树的高度差大于1则说明该节点不是平衡二叉树返回-1# 否则返回该节点的高度if (leftHeight : self.getHeight(root.left)) -1:return -1if (rightHeight : self.getHeight(root.right)) -1:return -1if abs(leftHeight - rightHeight) 1:return -1else:return 1 max(leftHeight, rightHeight)
