万网网站建设的子分类能显示多少个,专业制作广告,怎么做家具网站,外贸网站推广招聘这里写目录标题 一、104. 二叉树的最大深度二、100. 相同的树三、226. 翻转二叉树四、101. 对称二叉树 一、104. 二叉树的最大深度
简单 给定一个二叉树 root #xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 1、确定递归… 这里写目录标题 一、104. 二叉树的最大深度二、100. 相同的树三、226. 翻转二叉树四、101. 对称二叉树 一、104. 二叉树的最大深度
简单 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 1、确定递归函数的参数和返回值参数就是传入树的根节点返回就返回这棵树的深度所以返回值为int类型。 2、确定终止条件如果为空节点的话就返回0表示高度为0。 3、确定单层递归的逻辑先求它的左子树的深度再求右子树的深度最后取左右深度最大的数值 再1 加1是因为算上当前中间节点就是目前节点为根节点的树的深度。
class S104:def func(self, root):def dfs(root, depth):if not root: # 如果没有叶子节点返回深度return depthelse:return max(dfs(root.left, depth 1), dfs(root.right, depth 1))dfs(root, 0)二、100. 相同的树
简单 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 1、确定递归函数的参数和返回值参数就是传入两颗树返回值为True或者False。 2、确定终止条件
左节点为空右节点不为空return false左不为空右为空return false左右都为空返回true。左右节点都存在判断左节点的值与右节点的值是否相等如果不相等返回False
3、确定单层递归的逻辑p树的左子树q树的左子树p树的右子树q树的右子树
class S100:def func(self, p, q):if not p and not q:return Trueif not p:return Falseif not q:return Falseif p.val ! q.val:return Falsereturn self.func(p.left, q.left) and self.func(p.right, q.right)三、226. 翻转二叉树
简单 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 递归三部曲
1、确定递归函数的参数和返回值 参数就是要传入节点的指针不需要其他参数了 2、确定终止条件 当前节点为空的时候就返回 3、确定单层递归的逻辑 因为是先前序遍历所以先进行交换左右孩子节点然后反转左子树反转右子树。
class S226:def func(self, root):if not root:returnl self.func(root.left)r self.func(root.right)root.left rroot.right lreturn root四、101. 对称二叉树
简单 给你一个二叉树的根节点 root 检查它是否轴对称。 递归三部曲
1、确定递归函数的参数和返回值 因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。 2、确定终止条件 要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。
节点为空的情况有
左节点为空右节点不为空不对称return false左不为空右为空不对称 return false左右都为空对称返回true
此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空 左右都不为空比较节点数值不相同就return false 此时左右节点不为空且数值也不相同的情况我们也处理了。
3、确定单层递归的逻辑 此时才进入单层递归的逻辑单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。 比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。 比较内侧是否对称传入左节点的右孩子右节点的左孩子。 如果左右都对称就返回true 有一侧不对称就返回false 。
class S101:def func(self, root):def dfs(left, right):if not left and not right:return Trueelif not left and right:return Falseelif left and not right:return Falseelif left.val ! right.val:return Falseelse:return dfs(left.left, right.right) and dfs(left.right, right.left)return dfs(root.left, root.right)
