【leetcode强化练习·二叉树】同时运用两种思维解题
本文参考labuladong算法笔记[【强化练习】同时运用两种思维解题 | labuladong 的算法笔记]
有的题目可以同时用「遍历」和「分解问题」两种思路来解,你可以利用这些题目训练自己的思维。
559. N 叉树的最大深度 | 力扣 | LeetCode |
给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6] 输出:3
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出:5
提示:可以对照 104. 二叉树的最大深度 题的解法。
- 树的深度不会超过
1000
。 - 树的节点数目位于
[0, 104]
之间。
# 分解问题的思路
class Solution:
def maxDepth(self, root: 'Node') -> int:
if root is None:
return 0
subTreeMaxDepth = 0
for child in root.children:
subTreeMaxDepth = max(subTreeMaxDepth, self.maxDepth(child))
return 1 + subTreeMaxDepth
# 遍历的思路
class Solution:
def __init__(self):
# 记录递归遍历到的深度
self.depth = 0
# 记录最大的深度
self.res = 0
def maxDepth(self, root: 'Node') -> int:
self.traverse(root)
return self.res
def traverse(self, root: 'Node'):
if root is None:
return
# 前序遍历位置
self.depth += 1
self.res = max(self.res, self.depth)
for child in root.children:
self.traverse(child)
# 后序遍历位置
self.depth -= 1
112. 路径总和 | 力扣 | LeetCode |
给你二叉树的根节点 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 解释:由于树是空的,所以不存在根节点到叶子节点的路径。
提示:
- 树中节点的数目在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
基本思路
前文 我的刷题经验总结 说过,二叉树的遍历代码是动态规划和回溯算法的祖宗。
动态规划 的关键在于明确递归函数的定义,把用子问题的结果推导出大问题的结果。
回溯算法 就简单粗暴多了,就是单纯的遍历回溯树。
下面给出两种思路下的解法,请仔细体会。
class Solution:
# 解法一、分解问题的思路
# 定义:输入一个根节点,返回该根节点到叶子节点是否存在一条和为 targetSum 的路径
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
# base case
if root is None:
return False
# root.left == root.right 等同于 root.left == null && root.right == null
if root.left == root.right and root.val == targetSum:
return True
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
# 解法二、遍历二叉树的思路
# 记录遍历过程中的路径和
def hasPathSum_2(self, root: TreeNode, targetSum: int) -> bool:
if root is None:
return False
self.target = targetSum
self.found = False
self.curSum = 0
self.traverse(root)
return self.found
# 二叉树遍历函数
def traverse(self, root: TreeNode) -> None:
if root is None:
return
# 前序遍历位置
self.curSum += root.val
if root.left is None and root.right is None:
if self.curSum == self.target:
self.found = True
return
self.traverse(root.left)
self.traverse(root.right)
# 后序遍历位置
self.curSum -= root.val
113. 路径总和 II | 力扣 | LeetCode |
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
示例 2:
输入:root = [1,2,3], targetSum = 5 输出:[]
示例 3:
输入:root = [1,2], targetSum = 0 输出:[]
提示:
- 树中节点总数在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译。
# 本代码的正确性已通过力扣验证,如有疑问,可以对照 java 代码查看。
from typing import List, Optional
from collections import deque
class Solution:
def __init__(self):
self.res = []
def pathSum(self, root: Optional[TreeNode], sum: int) -> List[List[int]]:
if root is None:
return self.res
self.traverse(root, sum, deque())
return self.res
# 遍历二叉树
def traverse(self, root: Optional[TreeNode], sum: int, path: deque) -> None:
if root is None:
return
remain = sum - root.val
if root.left is None and root.right is None:
if remain == 0:
# 找到一条路径
path.append(root.val)
self.res.append(list(path))
path.pop()
return
# 维护路径列表
path.append(root.val)
self.traverse(root.left, remain, path)
self.traverse(root.right, remain, path)
path.pop()
# 分解问题的思维模式
class Solution2:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
if root is None:
return res
# 如果是叶子节点并且值等于 targetSum,则找到一条路径
if root.left is None and root.right is None and root.val == targetSum:
return [[root.val]]
# 分别递归左右子树,找到子树中和为 targetSum - root.val 的路径
left_answers = self.pathSum(root.left, targetSum - root.val)
right_answers = self.pathSum(root.right, targetSum - root.val)
# 左右子树的路径加上根节点,就是和为 targetSum 的路径
for answer in left_answers:
# 因为底层使用的是 LinkedList,所以这个操作的复杂度是 O(1)
answer.insert(0, root.val)
res.append(answer)
for answer in right_answers:
# 因为底层使用的是 LinkedList,所以这个操作的复杂度是 O(1)
answer.insert(0, root.val)
res.append(answer)
return res
类似题目:
- 1430. 判断给定的序列是否是二叉树从根到叶的路径 🟠
- 666. 路径总和 IV 🟠
- 剑指 Offer 34. 二叉树中和为某一值的路径 🟠
617. 合并二叉树 | 力扣 | LeetCode |
给你两棵二叉树: root1
和 root2
。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出:[3,4,5,5,4,null,7]
示例 2:
输入:root1 = [1], root2 = [1,2] 输出:[2,2]
提示:
- 两棵树中的节点数目在范围
[0, 2000]
内 -104 <= Node.val <= 104
虽然输入的是两棵树的根节点,但它们的操作是同步的,所以可以看做是在遍历 root1
这一棵二叉树,顺便把 root2
的节点合并过来。下面我给出两种思维模式的解法代码,具体看注释吧。
class Solution:
# 分解问题的思维模式
# 定义:输入两棵树的根节点,返回合并后的树的根节点
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
# 如果一棵树为空,那么合并后就是另一棵树
if root1 is None:
return root2
if root2 is None:
return root1
# 两棵树都有的节点,叠加节点值
root1.val += root2.val
# 利用函数定义,子树合并后接到
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
class Solution2:
# 遍历的思维模式
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if root1 is None:
return root2
# 遍历 root1,顺便把 root2 的节点合并过来
self.traverse(root1, root2)
return root1
def traverse(self, root1: TreeNode, root2: TreeNode):
if root1 is None or root2 is None:
return
# 两棵树都有的节点,叠加节点值
root1.val += root2.val
# 如果 root1 没有子树而 root2 有,那么就把 root2 的子树接到 root1 上
# 注意接完之后把 root2 的子树置为 null,免得错误计算节点累加值
if root1.left is None and root2.left is not None:
root1.left = root2.left
root2.left = None
if root1.right is None and root2.right is not None:
root1.right = root2.right
root2.right = None
# 递归遍历左右子节点,root2 的节点也跟着同步移动
self.traverse(root1.left, root2.left)
self.traverse(root1.right, root2.right)
897. 递增顺序搜索树 | 力扣 | LeetCode | 🟢
给你一棵二叉搜索树的 root
,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
示例 1:
输入:root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出:[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2:
输入:root = [5,1,7] 输出:[1,null,5,null,7]
提示:
- 树中节点数的取值范围是
[1, 100]
0 <= Node.val <= 1000
基本思路
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题可以同时用到两种思维模式。
「遍历」的话很简单,你对 BST 做中序遍历,其结果就是有序的,重新构造出题目要求的这个类似链表的二叉树即可。
「分解问题」的思路也不难,你只要做过 114. 二叉树展开为链表 这道题,稍微改下解法就可以解决这道题了,明确 increasingBST
的定义,然后利用这个定义进行操作即可。
# 输入一棵 BST,返回一个有序「链表」
class Solution:
# 分解问题思路
def increasingBST(self, root: TreeNode) -> TreeNode:
if root is None:
return None
# 先把左右子树拉平
left = self.increasingBST(root.left)
root.left = None
right = self.increasingBST(root.right)
root.right = right
# 左子树为空的话,就不用处理了
if left is None:
return root
# 左子树非空,需要把根节点和右子树接到左子树末尾
p = left
while p is not None and p.right is not None:
p = p.right
p.right = root
return left
class Solution:
# 遍历思路
def __init__(self):
# 建立虚拟头结点,后续新建节点都是dummy.right
self.dummy = TreeNode(0)
# 用cur指针去遍历dummy,拼接每一个新节点
self.cur = self.dummy
def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.traverse(root)
return self.dummy.right
def traverse(self, root):
if not root:
return
self.traverse(root.left)
self.cur.right = TreeNode(root.val)
self.cur = self.cur.right
self.traverse(root.right)
938. 二叉搜索树的范围和 | 力扣 | LeetCode | 🟢
给定二叉搜索树的根结点 root
,返回值位于范围 [low, high]
之间的所有结点的值的和。
示例 1:
输入:root = [10,5,15,3,7,null,18], low = 7, high = 15 输出:32
示例 2:
输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 输出:23
提示:
- 树中节点数目在范围
[1, 2 * 104]
内 1 <= Node.val <= 105
1 <= low <= high <= 105
- 所有
Node.val
互不相同
遍历的思路就是单纯用 traverse
函数遍历一遍 BST,找到落在区间的元素。分解问题的思路关键是要明确函数定义,然后利用这个定义。
class Solution:
# 遍历的思路
def __init__(self):
self.sum = 0
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
if root is None:
return 0
# 遍历一遍 BST 计算区间元素和
self.traverse(root, low, high)
return self.sum
def traverse(self, root: TreeNode, low: int, high: int):
if root is None:
return
if root.val < low:
# 目标区间在右子树
self.traverse(root.right, low, high)
elif root.val > high:
# 目标区间在左子树
self.traverse(root.left, low, high)
else:
# root.val 落在目标区间,累加 sum
self.sum += root.val
# 继续遍历左右子树
self.traverse(root.right, low, high)
self.traverse(root.left, low, high)
class Solution2:
# 分解问题的思路
# 定义:输入一个 BST,计算值落在 [low, high] 之间的元素之和
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
if root is None:
return 0
if root.val < low:
# 目标区间在右子树
return self.rangeSumBST(root.right, low, high)
elif root.val > high:
# 目标区间在左子树
return self.rangeSumBST(root.left, low, high)
else:
# 以 root 为根的这棵 BST 落在 [low, high] 之间的元素之和,
# 等于 root.val 加上左右子树落在区间的元素之和
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
1379. 找出克隆二叉树中的相同节点 | 力扣 | LeetCode | 🟢
给你两棵二叉树,原始树 original
和克隆树 cloned
,以及一个位于原始树 original
中的目标节点 target
。
其中,克隆树 cloned
是原始树 original
的一个 副本 。
请找出在树 cloned
中,与 target
相同 的节点,并返回对该节点的引用(在 C/C++ 等有指针的语言中返回 节点指针,其他语言返回节点本身)。
注意:你 不能 对两棵二叉树,以及 target
节点进行更改。只能 返回对克隆树 cloned
中已有的节点的引用。
示例 1:
输入: tree = [7,4,3,null,null,6,19], target = 3 输出: 3 解释: 上图画出了树 original 和 cloned。target 节点在树 original 中,用绿色标记。答案是树 cloned 中的黄颜色的节点(其他示例类似)。
示例 2:
输入: tree = [7], target = 7 输出: 7
示例 3:
输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 输出: 4
提示:
- 树中节点的数量范围为
[1, 104]
。 - 同一棵树中,没有值相同的节点。
target
节点是树original
中的一个节点,并且不会是null
。
进阶:如果树中允许出现值相同的节点,将如何解答?
说白了,这道题就是让你从一棵二叉树中搜索一个目标节点,考虑到题目的 follow up 问你节点的值存在重复的情况,所以用对比节点引用的方式进行比较。
# 遍历的思路
class Solution:
# 定义:找到 original 中 target 节点在 cloned 树中对应的节点
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
self.target = target
self.res = None
self.traverse(original, cloned)
return self.res
# 二叉树遍历函数
def traverse(self, original: TreeNode, cloned: TreeNode):
if original is None or self.res is not None:
return
if original == self.target:
self.res = cloned
return
# 二叉树遍历框架
self.traverse(original.left, cloned.left)
self.traverse(original.right, cloned.right)
# 分解问题的思路
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
if original is None:
return None
# 找到目标节点
if target == original:
return cloned
return self.getTargetCopy(original.left, cloned.left, target)\
or self.getTargetCopy(original.right, cloned.right, target)
1430. 判断给定的序列是否是二叉树从根到叶的路径 | 力扣 | LeetCode | 🟠
给定一个二叉树,我们称从根节点到任意叶节点的任意路径中的节点值所构成的序列为该二叉树的一个 “有效序列” 。检查一个给定的序列是否是给定二叉树的一个 “有效序列” 。
我们以整数数组 arr
的形式给出这个序列。从根节点到任意叶节点的任意路径中的节点值所构成的序列都是这个二叉树的 “有效序列” 。
示例 1:
输入:root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] 输出:true 解释: 路径 0 -> 1 -> 0 -> 1 是一个“有效序列”(图中的绿色节点)。 其他的“有效序列”是: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0
示例 2:
输入:root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1] 输出:false 解释:路径 0 -> 0 -> 1 不存在,所以这不是一个“序列”。
示例 3:
输入:root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1] 输出:false 解释:路径 0 -> 1 -> 1 是一个序列,但不是一个“有效序列”(译者注:因为序列的终点不是叶节点)。
提示:
1 <= arr.length <= 5000
0 <= arr[i] <= 9
- 每个节点的值的取值范围是
[0 - 9]
如果按照「遍历」的思路,这题和 113. 路径总和 II 有些像,一边遍历一边和 arr
数组对比。
如果按照「分解问题」的思路,关键要明确函数的定义,并且运用这个定义。
class Solution:
# 分解问题的思路解决本题
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
return self.check(root, arr, 0)
# 定义:输入一棵根为 root 的二叉树,
# 判断是否存在一条从根到叶子节点的路径的值为 arr[i..]
def check(self, root: TreeNode, arr: List[int], i: int) -> bool:
if root is None or i == len(arr):
return False
if root.left is None and root.right is None:
# 到达叶子结点,判断是否同时到达数组末端
return arr[i] == root.val and i == len(arr) - 1
if root.val != arr[i]:
return False
# 如果 root.val == arr[i],则判断子树是否存在一条路径值为 arr[i+1..]
return self.check(root.left, arr, i + 1) or self.check(root.right, arr, i + 1)
class Solution2:
# 遍历的思路解决本问题
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
self.arr = arr
self.traverse(root)
return self.isValid
# 记录遍历深度(函数的索引)
def __init__(self):
self.d = 0
self.arr = []
self.isValid = False
# 二叉树遍历函数
def traverse(self, root: TreeNode):
if root is None or self.isValid:
return
if root.left is None and root.right is None:
# 到达叶子结点,判断是否同时到达数组末端
if self.d == len(self.arr) - 1 and self.arr[self.d] == root.val:
self.isValid = True
return
if self.d >= len(self.arr) or self.arr[self.d] != root.val:
return
self.d += 1
# 二叉树遍历框架
self.traverse(root.left)
self.traverse(root.right)
self.d -= 1
1490. 克隆 N 叉树 | 力扣 | LeetCode | 🟠
给定一棵 N 叉树的根节点 root
,返回该树的深拷贝(克隆)。
N 叉树的每个节点都包含一个值( int
)和子节点的列表( List[Node]
)。
class Node { public int val; public List<Node> children; }
N 叉树的输入序列用层序遍历表示,每组子节点用 null 分隔(见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6] 输出:[1,null,3,2,4,null,5,6]
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出:[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
提示:
- 给定的 N 叉树的深度小于或等于
1000
。 - 节点的总个数在
[0, 104]
之间
进阶:你的解决方案可以适用于克隆图问题吗?
分解问题的思路:你想让我复制整棵树,那么我先复制根节点,然后递归调用 cloneTree
去复制所有子树(子问题)。
遍历的思路:这种递归数据结构的克隆问题,一般套路是遍历两次。第一次遍历用哈希表把原节点和克隆节点映射起来,第二次遍历把克隆节点组装起来。
# 遍历的思路
class Solution:
# 原始节点到复制节点的映射
def __init__(self):
self.nodeToCopy = {}
# 定义:输入 N 叉树节点,返回以该节点为根的 N 叉树的深拷贝
def cloneTree(self, root: 'Node') -> 'Node':
self.traverse1(root)
self.traverse2(root)
return self.nodeToCopy.get(root)
# 第一次遍历,构造每个节点的克隆
def traverse1(self, root: 'Node'):
if root is None:
return
# 拷贝节点,存到 nodeToCopy
cpRoot = Node(root.val)
self.nodeToCopy[root] = cpRoot
# 多叉树遍历框架
for child in root.children:
self.traverse1(child)
# 第二次遍历,组装克隆节点的结构
def traverse2(self, root: 'Node'):
if root is None:
return
# 组装克隆节点的结构
cpRoot = self.nodeToCopy[root]
cpRoot.children = []
for child in root.children:
cpRoot.children.append(self.nodeToCopy[child])
# 多叉树遍历框架
for child in root.children:
self.traverse2(child)
# 分解问题的思路
class Solution2:
# 定义:输入 N 叉树节点,返回以该节点为根的 N 叉树的深拷贝
def cloneTree(self, root: 'Node') -> 'Node':
if root is None:
return None
# 先拷贝根节点
cpRoot = Node(root.val)
# 根节点的孩子节点都是深拷贝
cpRoot.children = []
for child in root.children:
cpRoot.children.append(self.cloneTree(child))
# 返回整棵树的深拷贝
return cpRoot
总结
二叉树遍历的思路就像一个指针在整个树上游走,每到一个节点处理一次。这其中又涉及到前序/中序/后序不同问题场景的处理,应视情况灵活选用遍历方法。
二叉树分解问题的思路和回溯思路很像:
1、先明确递归终止条件/返回值
2、做单层/单个节点的处理(遇到符合条件的场景返回对应结果)
3、做子问题(子树)的递归处理