2023-12-14 二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数
2023-12-14 20:49:22
二叉树的最大深度和二叉树的最小深度以及完全二叉树的节点个数
104. 二叉树的最大深度
思想:可以使用迭代法或者递归!使用递归更好,帮助理解递归思路!明确递归三部曲–①确定参数以及返回参数 ②递归结束条件 ③单层逻辑是怎么样的!
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# 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 0
left_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, val=0, left=None, right=None):
# 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 0
left_length = deth_dp(node.left)
right_length = deth_dp(node.right)
# 还需要判断目前是否已经是叶子节点了
if not node.left and node.right:
return 1 + right_length
elif 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, val=0, left=None, right=None):
# 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 0
left_length = add_deth(node.left)
right_length = add_deth(node.right)
return 1 + left_length + right_length
return add_deth(root)
文章来源:https://blog.csdn.net/niuzai_/article/details/135002951
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!