代码随想录刷题记录（七）——二叉树（2）
这里写目录标题
- 二叉树
- 2. 相关题目
- 101. 对称二叉树
- 104.二叉树的最大深度
- 104.二叉树的最小深度
- 完全二叉树节点个数
- 110.平衡二叉树
- 257. 二叉树的所有路径
- 404.左叶子之和
- 513.找树左下角的值
- 112. 路径总和
二叉树
2. 相关题目
101. 对称二叉树
题目描述： 给定一个二叉树，检查它是否是镜像对称的。
思路： 遍历根节点的左右两个子树，比较它们的内侧和外侧。采用后序遍历
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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.compare(root.left, root.right)
def compare(self, left, right):
# 排除空节点的情况
if not left and right: return False
elif left and not right: return False
elif not left and not right: 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
2. 迭代法使用队列
import collections
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
queue = collections.deque()
queue.append(root.left) #将左子树头结点加入队列
queue.append(root.right) #将右子树头结点加入队列
while queue: #接下来就要判断这这两个树是否相互翻转
leftNode = queue.popleft()
rightNode = queue.popleft()
if not leftNode and not rightNode: #左节点为空、右节点为空，此时说明是对称的
continue
#左右一个节点不为空，或者都不为空但数值不相同，返回false
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
queue.append(leftNode.left) #加入左节点左孩子
queue.append(rightNode.right) #加入右节点右孩子
queue.append(leftNode.right) #加入左节点右孩子
queue.append(rightNode.left) #加入右节点左孩子
return True
3. 使用栈
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
st = [] #这里改成了栈
st.append(root.left)
st.append(root.right)
while st:
rightNode = st.pop()
leftNode = st.pop()
if not leftNode and not rightNode:
continue
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
st.append(leftNode.left)
st.append(rightNode.right)
st.append(leftNode.right)
st.append(rightNode.left)
return True
104.二叉树的最大深度
题目描述： 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
思路：
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从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 maxDepth(self, root: Optional[TreeNode]) -> int:
return self.getdepth(root)
def getdepth(self, node):
if not node:
return 0
leftheight = self.getdepth(node.left) # 左
rightheight = self.getdepth(node.right) # 右
height = 1 + max(leftheight, rightheight) # 中
return height
迭代法
# 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:
if not root:
return 0
depth = 0
queue = collections.deque([root])
while queue:
depth += 1
for _ in range(len(queue))；
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
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 minDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
if root.left is None and root.right is not None:
return self.minDepth(root.right)+1
if root.right is None and root.left is not None:
return self.minDepth(root.left)+1
return min(self.minDepth(root.right), self.minDepth(root.left))+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 minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
depth = 0
queue = collections.deque([root])
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
# 一层层遍历，直到有节点不存在左右子节点为止
if not node.left and not node.right:
return depth
if node.left: # 如果左子节点有值
queue.append(node.left)
if node.right: # 如果右子节点有值
queue.append(node.right)
return depth
完全二叉树节点个数
题目描述： 给出一个完全二叉树，求出该树的节点个数。
思路： 完全二叉树除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
递归法：
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
迭代法：
import collections
class Solution:
def countNodes(self, root: TreeNode) -> int:
queue = collections.deque()
if root:
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
result += 1 #记录节点数量
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
110.平衡二叉树
题目描述： 给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 isBalanced(self, root: Optional[TreeNode]) -> bool:
# 调用 getHeight 方法，如果返回值不为 -1，则树是平衡的
return self.getHeight(root) != -1
# 计算二叉树的高度，并检查是否平衡
def getHeight(self, root):
# 空节点的高度为 0
if not root:
return 0
# 递归计算左子树的高度
left_height = self.getHeight(root.left)
# 递归计算右子树的高度
right_height = self.getHeight(root.right)
# 如果左子树或右子树不平衡（返回了 -1），或者它们的相对高度差大于 1，则整棵树不平衡
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
# 如果当前节点的左右子树都平衡，则当前节点的高度为左右子树高度的最大值加 1
return max(left_height, right_height) + 1
257. 二叉树的所有路径
题目描述： 给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。
思路： 题目要求从根节点到叶子节点，需要用到前序遍历。并且使用回溯，将路径记录下来便于回退。具体实现方式：
（1）构造递归函数traversal，每次调用该函数都将当前节点的值添加到path列表中，path代表一条从root到当前节点的路径。
（2）每次检查当前节点是否为叶子节点，若果是，则将该path转换为字符串并存储到结果列表result中。
（3）如果存在左/右子节点，则递归调用traversal方法遍历左/右子树，完成遍历后，从path中移除当前节点的值（回溯）
递归法：
# 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 traversal(self, cur, path, result):
path.append(cur.val) # 中
if not cur.left and not cur.right: # 到达叶子节点，形成路径
tpath = '->'.join(map(str,path)) # map将path中的每个整数值转换为字符串，因为join需要对字符串进行串联。
result.append(tpath)
return
if cur.left: #如果左子节点存在
self.traversal(cur.left, path,result)
path.pop()
if cur.right: #如果右子节点存在
self.traversal(cur.right, path,result)
path.pop()
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
result = []
path = []
if not root:
return result
self.traversal(root, path, result)
return result
迭代法：
# 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]:
stack, path_st, result = [root],[str(root.val)], []
while stack:
cur = stack.pop()
path = path_st.pop()
# 如果当前节点为叶子节点，添加路径到结果中
if not (cur.left or cur.right):
result.append(path)
if cur.right: # 这里加入的顺序是右→左，弹出的顺序是左→右
stack.append(cur.right)
path_st.append(path + '->' + str(cur.right.val))
if cur.left:
stack.append(cur.left)
path_st.append(path + '->' + str(cur.left.val))
return result
404.左叶子之和
题目描述： 计算给定二叉树的所有左叶子之和
思路： 左叶子的定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点。判断方式：如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。
# 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:
if root is None:
return 0
if root.left is None and root.right is None:
return 0
leftValue = self.sumOfLeftLeaves(root.left) # 判断左子节点是否存在左叶子
if root.left and not root.left.left and not root.left.right:#左子树的特征，即节点的左子节点存在，但左子节点不存在子节点。
leftValue = root.left.val
rightValue = self.sumOfLeftLeaves(root.right) # 判断右子节点是否存在左叶子
sum_val = leftValue + rightValue
return sum_val
513.找树左下角的值
题目描述： 给定一个二叉树，在树的最后一行找到最左边的值
思路： 简单起见，可以采用层序遍历法
递归法
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
self.max_depth = float('-inf')
self.result = None
self.traversal(root, 0)
return self.result
def traversal(self, node, depth):
if not node.left and not node.right:
if depth > self.max_depth:
self.max_depth = depth
self.result = node.val
return
if node.left:
depth += 1
self.traversal(node.left, depth)
depth -= 1 # 完成后会回溯到上一层，所以depth-1
if node.right:
depth += 1
self.traversal(node.right, depth)
depth -= 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
from collections import deque
class Solution:
def findBottomLeftValue(self, root):
if root is None:
return 0
queue = deque()
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0: # 核心代码，遇到每一层的最左侧元素进行更新
result = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
112. 路径总和
题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。
思路：
（1）递归法
- 递归函数的参数与与返回类型：根节点和计数器；返回是否相等的布尔值
- 结束条件：遇到叶子结点，且路径和==目标值。在用计数器计算路径和时，不要去累加然后判断是否等于目标和，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
- 单层递归逻辑：更新计数器，检查叶子节点，如果当前节点不是叶子节点，递归地对左子节点和右子节点调用递归函数，并更新计数器。
递归法：
# 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 traversal(self, cur, count):
if not cur.left and not cur.right and count == 0: # 遇到叶子节点，且路径和等于目标
return True
if not cur.left and not cur.right: # 为什么这么写/
return False
if cur.left:
count -= cur.left.val # 计数器减去当前节点的值
if self.traversal(cur.left, count): # 递归，处理节点
return True
count += cur.left.val # 回溯，撤销处理结果
if cur.right:
count -= cur.right.val # 计数器减去当前节点的值
if self.traversal(cur.right, count): # 递归，处理节点
return True
count += cur.right.val # 回溯，撤销处理结果
return False # 遍历完了还是没有找到，返回false
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
return self.traversal(root, targetSum-root.val)
迭代法：
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
# 栈里放的是pair<节点指针，路径数值>
st = [(root, root.val)]
while st:
node, path_sum = st.pop()
# 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
if not node.left and not node.right and path_sum == targetSum:
return True
if node.right: # 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
st.append((node.right, path_sum+node.right.val))
if node.left: # 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
st.append((node.left, path_sum + node.left.val))
return False
return self.traversal(root, targetSum-root.val)