👾前言👾
二叉树是数据结构中一个非常重要的数据结构,他以节点之间凌乱的关系与图在数据结构中称霸一方。
掌握了树你就掌握了数据结构的左膀右臂。
那么问题来了：
如何创建二叉树呢？
如何搜索二叉树中的节点呢？
如何计算二叉树的最大深度？
如何判断平衡二叉树？
如何判断对称二叉树？
如何重建二叉树？
你也许一头雾水，你也许脑子中很快有了思路。
不妨先看一看如下几个练习题以巩固你对二叉树知识的掌握情况。
哦！二叉树好像还可以线索化，线索化是什么？如何线索化？
本章咱就不谈线索化了,感兴趣的小伙伴可以自己尝试一下。
或者在未来的不久,咱就出一期关于二叉树线索化的文章呢。
tips:大家一定要弄清二叉树的基本结构之后再来写下面几道题呀。
接下来咱们一块以学辅练,以练固学。迎接来自二叉树的冲击吧。
花非花树非树💦,希望对大家有帮助！
🍁前置知识🍁
树天生就是一种递归结构,所以使用递归的方法会使他的问题得到大大的简化。
二叉树是树的一个重要分支,二叉树中节点的子节点个数不超过2个（并且有顺序左、右）
前置知识呢就说这么多。其他的相信大家都已经会了。🤡
🤺练习题🤺
🌺二叉树的遍历🌺
💗问题描述💗
二叉树总共有四种遍历方式：
- 前序遍历：先遍历根节点然后遍历左子树、右子树
- 中序遍历：先遍历左子树在遍历根节点最后遍历右子树
- 后序遍历：先遍历左子树然后右子树最后根节点
- 层序遍历：使用队列一层一层向下遍历
💗问题分析💗
一般我们对树进行递归遍历,操作方式如下
💗代码实现💗
class myTree: def __init__(self,data): self.data=data self.left=None self.right=None def setLeft(self,p): self.left=p def setRight(self,p): self.right=p def getLeft(self): return self.left def getRight(self): return self.right def setData(self,data): self.data=data def getData(self): return self.data def creatTree(mytree): n=input("请输入该节点左子树数据(如果没有数据输入-1):") if n=='-1': return mytree.left=myTree(int(n)) creatTree(mytree.left) n=input("请输入该节点右子树数据(如果没有数据输入-1):") if n=='-1': return mytree.right=myTree(int(n)) creatTree(mytree.right) def lookTree1(mytree): if mytree!=None: print(mytree.data,end="") lookTree1(mytree.left) lookTree1(mytree.right) else: return def lookTree2(mytree): if mytree!=None: lookTree2(mytree.left) print(mytree.data,end="") lookTree2(mytree.right) else: return def lookTree3(mytree): if mytree!=None: lookTree3(mytree.left) lookTree3(mytree.right) print(mytree.data,end="") else: return # 根节点 mTree=myTree(0) # 建树 creatTree(mTree) # 前序遍历 print("前序遍历:",end="") lookTree1(mTree) print() # 中序遍历 print("中序遍历:",end="") lookTree2(mTree) print() # 后续遍历 print("后续遍历:",end="") lookTree3(mTree) print()
🌺二叉树的最大深度🌺
💗问题描述💗
力扣104题
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
💗问题分析💗
返回他最大深度的话咱们先思考以下几个问题：
- 父子节点之间深度有什么关系
- 两个子树深度不同应该如何选择
思考完这两个问题咱们看代码实现
💗代码实现💗
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root==None: return 0 return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
🌺对称二叉树🌺
💗问题描述💗
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false
💗问题分析💗
判断树是否哦对称,咱们应该判断对应位置的数据是否相同
我们首先想到的就是使用队列,因为只有队列才能保证访问节点的顺序
入队的时候应该先进行判断,如果有一个对应位置的节点为空一个不为空则肯定不对称
两个位置都为空的时候不用处理,然后将子节点成对放入队列中。每次循环取出一对节点进行判断
每次判断完将其左右子节点分别对应放入队列中。不对称就返回false，在筛选过程中只要有一个
false那么最终的结果就是false,类似于树的层序遍历。
💗代码实现💗
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if root==None or root.left==None and root.right==None: return True ls=[] ls.append(root.left) ls.append(root.right) while ls: t1=ls.pop() t2=ls.pop() if t1 and t2 and t1.val==t2.val: if t1.left==None and t2.right!=None or t1.left!=None and t2.right==None: return False if t2.left!=None and t1.right==None or t2.left==None and t1.right!=None: return False if t1.left!=None and t2.right!=None: ls.append(t1.left) ls.append(t2.right) if t1.right!=None and t2.left!=None: ls.append(t2.left) ls.append(t1.right) else: return False return True
🌺平衡二叉树🌺
💗问题描述💗
题目110
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
输入：root = [3,9,20,null,null,15,7]
输出：true
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
输入：root = []
输出：true
💗问题分析💗
判断是否平衡,就需要判断左子树右子树的深度,在第二个小练习中已经知道了怎么求二叉树的深度,所以我们可以进行求解左右子树的深度然后加以判断,将得到的深度进行返回,每次返回的还是最大深度
如果左右子树深度相差大于1,就返回-1,并加入判定条件如果某节点返回-1,那么接下来的返回结果均为-1
在第一次调用函数的地方进行判断返回值是不是-1得到结果。
下面给了两个解题方法：
第一个比较浪费空间时间不推荐使用,思想是每次判断该节点的左右子树深度是否符合规范,然后将判断的结果返回到上一层
第二个直接进行递归判断（只需要递归一次,判断是否符合要求即可。）
💗代码实现💗
# 先计算树的深度再计算左右子树的差值 # 重复进行了很多次计算 class Solution: def isBalanced(self, root: TreeNode) -> bool: if root==None: return True def maxdep(root): if root==None: return 0 return max(maxdep(root.left),maxdep(root.right))+1 return abs(maxdep(root.left)-maxdep(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right) #直接计算树是不是平衡二叉树 class Solution: def isBalanced(self, root: TreeNode) -> bool: if root==None: return True def maxdep(root): if root==None: return 0 left=maxdep(root.left) right=maxdep(root.right) if left==-1 or right==-1: return -1 if abs(left-right)>1: return -1 return max(left,right)+1 return maxdep(root)!=-1
🌺重建二叉树🌺
💗问题描述💗
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
输入: preorder = [-1], inorder = [-1]
输出: [-1]
💗问题分析💗
二叉树有许多性质,如果给出他的前序遍历与中序遍历，那么可以建出这个树,并且得到后续遍历
给出后续遍历与中序遍历也是如此
利用的思想就是,前序遍历第一个顶点肯定是根节点
然后接下来一段是左子树,然后是右子树
中序遍历中左子树在根节点左边,右子树在其右边。
根据这个关系我们可以写出以下递归。
💗代码实现💗
# 树体结构 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 后序遍历 def pTree(root): if root.left!=None: pTree(root.left) if root.right!=None: pTree(root.right) print(root.val,end="") # 重建二叉树 def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode: if not preorder and not inorder: return None root=TreeNode() root.val=preorder[0] t=inorder.index(preorder[0]) root.left=buildTree(preorder[1:t+1],inorder[:t]) root.right=buildTree(preorder[t+1:],inorder[t+1:]) return root pTree(buildTree([3,9,20,15,7],[9,3,15,20,7]))
