Day 15 卡玛笔记
这是基于代码随想录的每日打卡
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
递归法
# 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:
if root==None:
return 0
def count_node(node):
# 终止条件：节点为None返回0
if node==None:
return 0
# 处理单层逻辑
leftnum=count_node(node.left) # 左孩子数量
rightnum=count_node(node.right) # 右孩子数量
return 1+leftnum+rightnum
return count_node(root)
运行结果
110. 平衡二叉树
给定一个二叉树，判断它是否是平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
递归法
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
def getHeight(node):
# 递归终止条件
if node==None:
return 0
# 单层逻辑
# 左子树高度
left=getHeight(node.left)
# 如果左子树返回-1，则当层直接返回-1
if left==-1:
return -1
# 右子树高度
right=getHeight(node.right)
# 如果右子树返回-1，则当层直接返回-1
if right==-1:
return -1
# 如果左右子树都符合条件，计算整体是否符合条件
if abs(left-right)>1:
# 如果不符合条件返回给上层-1
return -1
else:
# 如果符合条件，则返回当前节点高度给上一层
return 1+max(left,right)
res=getHeight(root)
if res!=-1:
return True
else:
return False
运行结果
404. 左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1]
输出: 0
递归法
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def Count(node):
# 递归终止条件
if node==None:
return 0
# 处理单层逻辑
# 计算左子树的左叶子之和
if node.left!=None and node.left.left==None and node.left.right==None:
leftvalue=node.left.val
else:
leftvalue=Count(node.left)
# 计算右子树的左叶子之和
rightvalue=Count(node.right)
return leftvalue+rightvalue
return Count(root)
运行结果
257. 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
输入：root = [1]
输出：["1"]
递归法
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res=[]
path=[]
def traversal(node,res,path):
# 终止条件
# 当走到叶子节点时就是终点了
if node.left==None and node.right==None:
path.append(node.val)
res.append('->'.join(map(str,path)))
return
# 递归逻辑
path.append(node.val)
if node.left:
traversal(node.left,res,path)
# 回溯
path.pop()
if node.right:
traversal(node.right,res,path)
# 回溯
path.pop()
traversal(root,res,path)
return res
运行结果
有问题欢迎评论或私信