爱站网络科技有限公司,浦江网站建设微信开发,专业做写生的网站,怎样注册网站卖东西二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数
104. 二叉树的最大深度 思想#xff1a;可以使用迭代法或者递归#xff01;使用递归更好#xff0c;帮助理解递归思路#xff01;明确递归三部曲–①确定参数以及返回参数 ②递归结束条件 ③单层逻辑是怎么样…二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数
104. 二叉树的最大深度 思想可以使用迭代法或者递归使用递归更好帮助理解递归思路明确递归三部曲–①确定参数以及返回参数 ②递归结束条件 ③单层逻辑是怎么样的
# 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 maxDepth(self, root: Optional[TreeNode]) - int:# 确定递归的参数以及返回# 什么时候结束递归# 递归的单层逻辑是怎么样的def dp(node):if not node:return 0left_length dp(node.left)right_length dp(node.right)return 1 max(left_length, right_length)return dp(root)
111. 二叉树的最小深度 思想看似和最大深度相似实则不同的还需要考虑一个节点为None但是另一个不为None的情况这个是关键如果是参加面试最好使用迭代法来做也就是广度优先遍历这样会更快更好理解【判断节点是否有左右节点即可】
# 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 minDepth(self, root: Optional[TreeNode]) - int:# 使用递归的方法--参数为TreeNode 返回int结束条件左右节点皆为None单层逻辑def deth_dp(node):if not node:return 0left_length deth_dp(node.left)right_length deth_dp(node.right)# 还需要判断目前是否已经是叶子节点了if not node.left and node.right:return 1 right_lengthelif node.left and not node.right:return 1 left_length# 最后都为None 直接比较返回就好了return 1 min(left_length, right_length)return deth_dp(root)222. 完全二叉树的节点个数 思想和最大深度很像返回值等于左右节点相加即可
# 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 countNodes(self, root: Optional[TreeNode]) - int:def add_deth(node):if not node:return 0left_length add_deth(node.left)right_length add_deth(node.right)return 1 left_length right_lengthreturn add_deth(root)
