网站快速备案多少钱认证,WordPress主题怎么翻译,网页设计与制作自考,中国工程造价网226.翻转二叉树
给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。 使用递归解决。
确定函数参数和返回值 函数参数为当前节点cur。无返回值。
def dd(cur):确定终止条件。当前节点为空则终止。
if not cur:return 单层逻辑 反转当前…226.翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 使用递归解决。
确定函数参数和返回值 函数参数为当前节点cur。无返回值。
def dd(cur):确定终止条件。当前节点为空则终止。
if not cur:return 单层逻辑 反转当前节点的左右然后递归调用cur.left, cur.right def dd(cur):if not cur:return cur.left, cur.right cur.right, cur.leftdd(cur.left)dd(cur.right)完整代码如下
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:def dd(cur):if not cur:return cur.left, cur.right cur.right, cur.leftdd(cur.left)dd(cur.right)dd(root)return root101.对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
这题用层序遍历很好做只要判断每层是不是对称的就好了空的节点添加一个特殊值方便判断对称。
# 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 isSymmetric(self, root: Optional[TreeNode]) - bool:def symmetric_list(lst):length len(lst)i 0j length-1while i j:if lst[i] ! lst[j]:return Falsei 1j - 1return Trueres []if not root:return resqueue deque()queue.append(root)while len(queue) 0:next_list []length len(queue)for i in range(length):node queue.popleft()if node.left:queue.append(node.left)next_list.append(node.left.val)else:next_list.append(-9999)if node.right:queue.append(node.right)next_list.append(node.right.val)else:next_list.append(-9999)if not symmetric_list(next_list):return Falsereturn True递归方式有点绕因为要判断的是轴对称。
函数参数和返回值。 参数是左子节点和右子节点。返回值是 bool值表示是否当前节点是否轴对称。
def compare(left, right): 终止条件。 左右节点全为空或某个为空时则可以判断出当前节点的左右是否是对称的了。
if not left and not right:return True
elif not left or not right:return False 单层逻辑
return left.val right.val and \compare(left.left, right.right) and compare(left.right, right.left) 104.二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
层序遍历非常直接遍历的层数就是深度。
class Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:res []if not root:return resqueue deque()queue.append(root)while len(queue) 0:sub_list []length len(queue) # 注意for i in range(length):node queue.popleft()sub_list.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(sub_list)return resdef maxDepth(self, root: Optional[TreeNode]) - int:res self.levelOrder(root)return len(res)递归更简单
函数参数和返回值。 参数为当前节点node。返回值为int值表示节点的深度。终止条件 节点为空时返回0.单层逻辑 max(左节点深度,右节点深度) 1
class Solution:def maxDepth(self, root: Optional[TreeNode]) - int:def depth(node):if not node:return 0leftDepth depth(node.left)rightDepth depth(node.right)return max(leftDepth, rightDepth)1return depth(root)二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。 本题可以使用前序遍历中左右也可以使用后序遍历左右中使用前序求的就是深度使用后序求的是高度。 而根节点的高度就是二叉树的最大深度所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
111.二叉树的最小深度
给定一个二叉树找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
这题层序遍历还是很简单因为每遍历一层就对应深度1。如果找到了叶子节点就可以终止遍历返回当前深度了。
class Solution:def minDepth(self, root: Optional[TreeNode]) - int:if not root:return 0queue deque()queue.append(root)depth 0while queue:depth 1length len(queue)for i in range(length):node queue.popleft()if all([not node.left, not node.right]):return depth for nextnode in [node.left, node.right]:if nextnode:queue.append(nextnode)return depth递归方式。 递归方式和104求最大深度差很多。最小深度必须是根节点到叶子节点的长度如果左子树为空右子树不为空则只能通过右子树到达叶子节点(1rightDepth)。
递归公式
函数参数和返回值。 参数为当前节点node。返回值为int值表示节点的深度。终止条件 节点为空时返回0.单层逻辑 如果只有右子树返回 1rightDepth 如果只有左子树返回 1leftDepth 否则返回 min(左节点深度,右节点深度) 1
class Solution:def minDepth(self, root: Optional[TreeNode]) - int:def getDepth(node: Optional[TreeNode]) - int:if not node :return 0leftDepth getDepth(node.left)rightDepth getDepth(node.right)if not node.left and node.right :return 1 rightDepthif not node.right and node.left:return 1 leftDepthreturn 1 min(leftDepth, rightDepth)return getDepth(root)222.完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
遍历一次就知道节点个数了。 但是这样就没有用到完全二叉树的性质。
完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满。 对于情况一可以直接用 2^树深度 - 1 来计算注意这里根节点深度为1。 对于情况二分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。
递归公式 函数参数和返回值。 参数是当前节点。返回值是当前节点为根节点的树的节点个数。 终止条件 如果节点为None返回0。 单层逻辑 判断当前节点是不是满二叉树是满二叉树则直接用公式2^树深度 - 1 返回节点数。否则递归处理左右子树返回左子树节点数 右子树节点数 1。
class Solution:def countNodes(self, root: Optional[TreeNode]) - int:if not root:return 0# 判断当前节点是不是满二叉树leftHeight, rightHeight 0, 0left, right root.left, root.rightwhile left:left left.leftleftHeight 1while right:right right.rightrightHeight 1# 是满二叉树则用公式计算if leftHeight rightHeight:return (2 leftHeight) -1# 否则递归处理left, rightreturn self.countNodes(root.left) self.countNodes(root.right) 1110.平衡二叉树
给定一个二叉树判断它是否是高度平衡的二叉树。 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。
LeetCode上的不是按照路径数而是按照节点数计算。
求深度可以从上到下去查 所以需要前序遍历中左右而高度只能从下到上去查所以只能后序遍历左右中。
递归公式
函数参数和返回值 参数为当前节点返回值为节点的高度。返回值为-1时表示不是平衡二叉树。终止条件 节点为None返回0。单层逻辑 求左子树高度如果为-1则已经不平衡了返回-1. 求右子树高度如果为-1则已经不平衡了返回-1. 如果左右子树高度差1不平衡返回-1. 否则返回当前节点的高度1 max(leftDepth, rightDepth)
class Solution:def isBalanced(self, root: Optional[TreeNode]) - bool:def getHeight(node):if not node:return 0leftDepth getHeight(node.left)if leftDepth -1: return -1rightDepth getHeight(node.right)if rightDepth -1: return -1if abs(leftDepth - rightDepth) 1:return -1else:return 1 max(leftDepth, rightDepth)return not getHeight(root) -1257.二叉树的所有路径
按 任意顺序 返回所有从根节点到叶子节点的路径。
递归回溯。 递归公式
参数和返回值 参数是当前节点、路径、存放结果的数组。返回值无。终止条件 到达叶子节点。单层逻辑 添加当前节点递归回溯遍历左子树和右子树。
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]:def traversal(cur, path, result):path.append(cur.val) # 终止条件到达叶子节点了 if not any([cur.left, cur.right]):sPath for n in path:sPath str(n)sPath -sPath sPath[:-2]result.append(sPath)return# 左子树 if cur.left:traversal(cur.left, path, result)path.pop() # 回溯# 右子树 if cur.right:traversal(cur.right, path, result)path.pop()result []path []if not root:return resulttraversal(root, path, result)return result404.左叶子之和
给定二叉树的根节点 root 返回所有左叶子之和。 左叶子是父节点的左节点并且是叶子节点。
递归公式
函数参数和返回值 参数是当前节点返回值是当前节点的左叶子之和。终止条件 当前节点为None返回0.单层逻辑 如果当前节点是左叶子则要加入当前节点的值。然后加上左子树的左叶子和右子树的左叶子和。
class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) - int:def getLeft(node):if not node:return 0leftValue getLeft(node.left)rightValue getLeft(node.right)midValue 0# 左叶子# 它是父节点的左节点同时它是叶子节点if node.left and node.left.left None and node.left.right None:midValue node.left.val return midValue leftValue rightValuereturn getLeft(root)513.找树左下角的值
给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
层序遍历比较简单遍历完然后获取最后一层的第一个节点。
# 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: Optional[TreeNode]) - List[List[int]]:res []if not root:return resqueue deque()queue.append(root)while queue:sub_list []length len(queue)for i in range(length):node queue.popleft()sub_list.append(node.val)for nextnode in [node.left, node.right]:if nextnode:queue.append(nextnode)res.append(sub_list)return resdef findBottomLeftValue(self, root: Optional[TreeNode]) - int:return self.levelOrder(root)[-1][0]递归方式。 递归找最底层最左的节点需要知道层数。 递归公式
函数参数和返回值。 参数是当前节点和当前层数。终止条件 到达叶子节点。单层逻辑 递归处理左子树和右子树深度1.
class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) - int:maxDepth -11111 # 最大深度maxLeftValue 0 # 最深层 最左的节点值def traversal(root, depth):nonlocal maxDepth, maxLeftValue# 终止条件 到达叶子if not root.left and not root.right:# 深度是最深的更新答案if depth maxDepth:maxDepth depthmaxLeftValue root.valreturn# 递归处理左右if root.left:traversal(root.left, depth1) # 隐藏回溯if root.right:traversal(root.right, depth1)return traversal(root,0)return maxLeftValue112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。 递归公式
函数参数和返回值 参数当前节点root目标和targetSum。 返回值bool值表示是否满足题目要求。终止条件 当前节点为None返回False单层逻辑 如果是叶子节点判断当前值和目标值是否相等。 否则对左、右子数递归判断。
class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) - bool:if not root:return Falseif not root.left and not root.right:return root.val targetSumreturn self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)
