wordpress地区分站,个人网站建设知乎,网站设计师的岗位职责,广州海珠网站设计226.翻转二叉树 翻转一棵二叉树。 思路#xff1a;
在这里需要注意的是#xff0c;在递归的时候唯独中序遍历是不可用的#xff0c;这是因为先对左子树进行了反转#xff0c;又对自身进行了反转#xff0c;对自身反转后原本的左子树变成了右子树#xff0c;如果此时又轮…226.翻转二叉树 翻转一棵二叉树。 思路
在这里需要注意的是在递归的时候唯独中序遍历是不可用的这是因为先对左子树进行了反转又对自身进行了反转对自身反转后原本的左子树变成了右子树如果此时又轮到对右子树进行翻转相当于原本的右子树没操作而对原来的左子树进行了两次翻转。 所以我们选择前序遍历根据递归三部曲
1.确定参数和返回值参数是节点而返回值可以是返回根节点但我个人在一开始做的时候人为自定义了一个新的函数来专门对二叉树进行反转是直接对二叉树进行操作的所以认为不需要返回值选择void或者-None
2.确定终止条件当左孩子和右孩子都不存在的时候说明此时翻转无意义此时return。但规范写法的思路是当节点为空的时候return我想这是因为如果只有一个左右孩子的时候依然会调用函数这个时候有一个孩子节点是为空的所以此时在定义递归函数的时候肯定还是需要定义一个条件当节点为空时return自然就不需要我一开始设置的这个条件了
3.单层递归的逻辑我选择最好理解的前序遍历逻辑就是先对本节点进行操作即对本节点的左右孩子进行互换然后对左子树左孩子节点进行反转操作调用递归再对右子树进行反转操作。 根据以上思路实现代码如下
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def reverseTree(self, node: Optional[TreeNode]) - None:if not node:returnif not node.left and not node.right:returnnode.left, node.right node.right, node.leftself.reverseTree(node.left)self.reverseTree(node.right)def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:if not root:return rootself.reverseTree(root)return root 附上规范写法更简洁和有效应该学习
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def invertTree(self, root: TreeNode) - TreeNode:if not root:return Noneroot.left, root.right root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return root 以上是递归写法自然还能用迭代的方法个人更喜欢使用广度优先层序遍历非常好理解思路就是层序遍历压入队列中然后依次进行反转代码实现如下
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def invertTree(self, root: TreeNode) - TreeNode:if not root:return rootqueue deque([root])while(queue):for _ in range(len(queue)):cur queue.popleft()if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)cur.left, cur.right cur.right, cur.leftreturn root 101. 对称二叉树 给定一个二叉树检查它是否是镜像对称的。 思路
第一反应还是层序遍历只需要将包括None的每一层节点数组都压入数组中如果将数组的每一层数组反序输出与原数组都相同那么说明是对称的。
但还是以学习递归为主先优先实现递归的方法思路是在每一个递归过程中判断【左孩子的左孩子】和【右孩子的右孩子】是否相等以及判断【左孩子的右孩子】和【右孩子的左孩子】是否相等。代码随想录将其分别称为外侧和里侧可能更好理解一点。除了以上还需要确保根节点的左右孩子相等才行。 递归三部曲
参数和返回值参数为两个是左右孩子两个节点即要进行比较的两个子树根节点。返回值应该是bool当出现任意一个false都应该返回false。终止条件①左空右不空-false ②左不空右空-false ③左右为空-True ④左右不空但数值不等-false递归逻辑当左右不空且数值相等时这里其实是⑤所以上面④的时候不能用else只能用else if或者elif才进入递归逻辑判断【左孩子的右孩子】和【右孩子的左孩子】是否相等只有当两个条件都符合时返回True否则返回false。 代码实现如下
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def compare(self, node1: Optional[TreeNode], node2: Optional[TreeNode]) - bool:if node1 and not node2:return Falseelif not node1 and node2:return Falseelif not node1 and not node2:return Trueelif node1.val ! node2.val:return Falsebool1 self.compare(node1.left, node2.right)bool2 self.compare(node1.right, node2.left)return bool1 and bool2def isSymmetric(self, root: Optional[TreeNode]) - bool:if not root:return Trueif not root.left and not root.right:return Truereturn self.compare(root.left, root.right) 规范代码
class Solution:def isSymmetric(self, root: TreeNode) - bool:if not root:return Truereturn self.compare(root.left, root.right)def compare(self, left, right):#首先排除空节点的情况if left None and right ! None: return Falseelif left ! None and right None: return Falseelif left None and right None: return True#排除了空节点再排除数值不相同的情况elif left.val ! right.val: return False#此时就是左右节点都不为空且数值相同的情况#此时才做递归做下一层的判断outside self.compare(left.left, right.right) #左子树左、 右子树右inside self.compare(left.right, right.left) #左子树右、 右子树左isSame outside and inside #左子树中、 右子树中 逻辑处理return isSame 层序遍历
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def isSymmetric(self, root: Optional[TreeNode]) - bool:if not root:return Trueres []queue deque([root])while queue:arr []for _ in range(len(queue)):cur queue.popleft()if not cur:arr.append(None)continuearr.append(cur.val)queue.append(cur.left)queue.append(cur.right)res.append(arr)for arr in res:if arr ! arr[::-1]:return Falsereturn True 规范代码层序遍历
class Solution:def isSymmetric(self, root: TreeNode) - bool:if not root:return Truequeue collections.deque([root.left, root.right])while queue:level_size len(queue)if level_size % 2 ! 0:return Falselevel_vals []for i in range(level_size):node queue.popleft()if node:level_vals.append(node.val)queue.append(node.left)queue.append(node.right)else:level_vals.append(None)if level_vals ! level_vals[::-1]:return Falsereturn True 104.二叉树的最大深度 给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 给定二叉树 [3,9,20,null,null,15,7] 返回它的最大深度 3 。 思路
依然第一反应是层序遍历:每到新一层就更新最大值最后返回最大值即可。
还是以学习递归为主递归思路
节点的深度是孩子节点的深度1那么只需要递归计算孩子节点的深度然后1即可。 递归三部曲
参数和返回值参数应该是传入一个节点。返回值是传入节点的两个孩子节点的深度的最大值应该是int类型。终止条件当左右孩子都不存在的时候说明是叶子节点此时返回深度1。当本节点不存在的时候这时候为了区别于叶子节点返回深度0递归逻辑对两个左右孩子进行递归调用得到两个数值中的最大值然后再1就可以得到当前节点的深度。 代码实现如下
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def getdepth(self, node: Optional[TreeNode]) - int:if not node:return 0if not node.left and not node.right:return 1return max(self.getdepth(node.left), self.getdepth(node.right)) 1def maxDepth(self, root: Optional[TreeNode]) - int:if not root:return 0return self.getdepth(root) 层序遍历
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def maxDepth(self, root: Optional[TreeNode]) - int:if not root:return 0queue deque([root])res 0while queue:for _ in range(len(queue)):cur queue.popleft() if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)res 1return res 111.二叉树的最小深度 给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2. 思路
层序遍历思路每层遍历记录层数当第一次遍历到叶子节点的时候直接返回深度即可。 递归思路与前面计算最大深度相似但是需要注意的是有一种情况不一样也就是只有一个孩子的情况因为没有孩子的情况有可能会返回0但此时本节点并非叶子节点此时如果空节点返回了深度0那么此时计算到的最小深度是错误的。所以该题应该在遇到空孩子的时候直接跳过。 递归三部曲
参数和返回值参数是进入递归调用的节点。返回值应该是int类型的深度值。终止条件当左右孩子都不存在时为叶子节点返回深度1递归逻辑当左右孩子均存在时计算两个孩子节点的深度的最小值得到后1作为返回值。如果只存在一个孩子则计算存在的孩子节点的深度然后1作为返回值。、 代码实现如下
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def minDepth(self, root: Optional[TreeNode]) - int:return self.getdepth(root)def getdepth(self, node: Optional[TreeNode]) - int:if not node:return 0if not node.left and not node.right:return 1if node.left and node.right:return min(self.getdepth(node.left), self.getdepth(node.right)) 1elif not node.left and node.right:return self.getdepth(node.right) 1elif node.left and not node.right:return self.getdepth(node.left) 1 规范代码
class Solution:def getDepth(self, node):if node is None:return 0leftDepth self.getDepth(node.left) # 左rightDepth self.getDepth(node.right) # 右# 当一个左子树为空右不为空这时并不是最低点if node.left is None and node.right is not None:return 1 rightDepth# 当一个右子树为空左不为空这时并不是最低点if node.left is not None and node.right is None:return 1 leftDepthresult 1 min(leftDepth, rightDepth)return resultdef minDepth(self, root):return self.getDepth(root) 层序遍历
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def minDepth(self, root: Optional[TreeNode]) - int:if not root:return 0queue deque([root])res 0while queue:for _ in range(len(queue)):cur queue.popleft() if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)if not cur.left and not cur.right:return res1res 1return res
