二叉树 递归

本篇基于b站灵茶山艾府的课上例题与课后作业。

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

---

# 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:# 方法1:自底向上（归）# def dfs(node):#     if node == None:#         return 0#     return max(dfs(node.left), dfs(node.right)) + 1# return dfs(root)# 方法2：自顶向下（递）ans = 0     def dfs(node, cnt):if node == None:returnnonlocal ansans = max(ans, cnt)dfs(node.left, cnt + 1)dfs(node.right, cnt + 1)dfs(root, 1)return ans

---

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

---

# 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:# 方法1：自底向上（归）# def dfs(root):#     # 由于是找从根节点到最近 叶子 节点的深度，所以我们的边界条件是判断叶子节点，而不是单单空节点#     if root.left == None and root.right == None:#         return 1#     if root.left == None and root.right != None:#         return dfs(root.right) + 1#     if root.right == None and root.left != None:#         return dfs(root.left) + 1#     return min(dfs(root.left), dfs(root.right)) + 1# if root == None:#     return 0# return dfs(root)# 方法2：自顶向下（归）ans = float("inf")def dfs(root, cnt):nonlocal ansif cnt >= ans:  # 剪枝，继续往下递也不会让cnt变小returnif root.left == None and root.right == None:ans = min(cnt, ans)returnelif root.left == None and root.right != None:dfs(root.right, cnt + 1)elif root.right == None and root.left != None:dfs(root.left, cnt + 1)else:dfs(root.left, cnt + 1)dfs(root.right, cnt + 1)if root == None:return 0dfs(root, 1)return ans

---

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

---

# 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:# 若根节点有左孩子，那么可以将问题分解为从左孩子到它的叶子节点的路径总和是否等于target-root.val# 若有右孩子也是同理，从而将此问题分解为一个个子问题def dfs(root, target):# 这道题边界条件还是题目所说的叶子节点if root.left == None and root.right == None:if target == root.val:return Trueelse:return False# 加这两个判断是为了下面的return，避免dfs里面传入了空节点报错if root.left == None and root.right != None:return dfs(root.right, target - root.val)if root.right == None and root.left != None:return dfs(root.left, target - root.val)return dfs(root.left, target - root.val) or dfs(root.right, target - root.val)if root == None:return Falsereturn dfs(root, targetSum)

---

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

---

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:ans = 0# val存储路径上的数字，用字符串拼接def dfs(root, val):nonlocal ansif root.left == None and root.right == None:# 当遇到叶子节点，拼接后记录结果ans += int(val + str(root.val))elif root.left == None and root.right != None:return dfs(root.right, val + str(root.val))elif root.right == None and root.left != None:return dfs(root.left, val + str(root.val))else:dfs(root.left, val + str(root.val))dfs(root.right, val + str(root.val))dfs(root, "")return ans

---

1448. 统计二叉树中好节点的数目

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

示例 1：

输入：root = [3,1,4,3,null,1,5]
输出：4
解释：图中蓝色节点为好节点。
根节点 (3) 永远是个好节点。
节点 4 -> (3,4) 是路径中的最大值。
节点 5 -> (3,4,5) 是路径中的最大值。
节点 3 -> (3,1,3) 是路径中的最大值。

示例 2：

输入：root = [3,3,null,4,2]
输出：3
解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。

示例 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 goodNodes(self, root: Optional[TreeNode]) -> int:ans = 0# 传入参数的val表示当前节点之前所有可能的路径中节点的最大值def dfs(root, val):nonlocal ansif root == None:return# 如果遇到的节点比最大值大，说明前面的节点一定比当前节点小，则记录结果，同时更新最大值if root.val >= val:val = root.valans += 1dfs(root.right, val)dfs(root.left, val)dfs(root, -10001)return ans

---

987. 二叉树的垂序遍历

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例 2：

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。1 在上面，所以它出现在前面。5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例 3：

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

---

# 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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:from collections import defaultdict#哈希表，键为节点所在的列，值为（行，值）li = defaultdict(list)def dfs(root, i, j):if root == None:returnli[j].append((i, root.val))dfs(root.left, i + 1, j - 1)dfs(root.right, i + 1, j + 1)dfs(root, 0, 0)res = []# sorted*(li.items()):给哈希表中按键排序for key, values in sorted(li.items()):# 给值里面的列表排序，列表里面为元组，排序依据为元组的第一个值，再第二个值values.sort()res.append([i[1] for i in values])return res