【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 0subTreeMaxDepth = 0for child in root.children:subTreeMaxDepth = max(subTreeMaxDepth, self.maxDepth(child))return 1 + subTreeMaxDepth# 遍歷的思路
class Solution:def __init__(self):# 記錄遞歸遍歷到的深度self.depth = 0# 記錄最大的深度self.res = 0def maxDepth(self, root: 'Node') -> int:self.traverse(root)return self.resdef traverse(self, root: 'Node'):if root is None:return# 前序遍歷位置self.depth += 1self.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 caseif root is None:return False# root.left == root.right 等同于 root.left == null && root.right == nullif root.left == root.right and root.val == targetSum:return Truereturn 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 Falseself.target = targetSumself.found = Falseself.curSum = 0self.traverse(root)return self.found# 二叉樹遍歷函數def traverse(self, root: TreeNode) -> None:if root is None:return# 前序遍歷位置self.curSum += root.valif root.left is None and root.right is None:if self.curSum == self.target:self.found = Truereturn 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 dequeclass Solution:def __init__(self):self.res = []def pathSum(self, root: Optional[TreeNode], sum: int) -> List[List[int]]:if root is None:return self.resself.traverse(root, sum, deque())return self.res# 遍歷二叉樹def traverse(self, root: Optional[TreeNode], sum: int, path: deque) -> None:if root is None:returnremain = sum - root.valif 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 root2if 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 root1class Solution2:# 遍歷的思維模式def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if root1 is None:return root2# 遍歷 root1，順便把 root2 的節點合并過來self.traverse(root1, root2)return root1def 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.leftroot2.left = Noneif root1.right is None and root2.right is not None:root1.right = root2.rightroot2.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 = Noneright = self.increasingBST(root.right)root.right = right# 左子樹為空的話，就不用處理了if left is None:return root# 左子樹非空，需要把根節點和右子樹接到左子樹末尾p = leftwhile p is not None and p.right is not None:p = p.rightp.right = rootreturn leftclass Solution:# 遍歷思路def __init__(self):# 建立虛擬頭結點，后續新建節點都是dummy.rightself.dummy = TreeNode(0)# 用cur指針去遍歷dummy，拼接每一個新節點self.cur = self.dummydef increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.traverse(root)return self.dummy.rightdef traverse(self, root):if not root:returnself.traverse(root.left)self.cur.right = TreeNode(root.val)self.cur = self.cur.rightself.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 = 0def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:if root is None:return 0# 遍歷一遍 BST 計算區間元素和self.traverse(root, low, high)return self.sumdef traverse(self, root: TreeNode, low: int, high: int):if root is None:returnif root.val < low:# 目標區間在右子樹self.traverse(root.right, low, high)elif root.val > high:# 目標區間在左子樹self.traverse(root.left, low, high)else:# root.val 落在目標區間，累加 sumself.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 0if 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 = targetself.res = Noneself.traverse(original, cloned)return self.res# 二叉樹遍歷函數def traverse(self, original: TreeNode, cloned: TreeNode):if original is None or self.res is not None:returnif original == self.target:self.res = clonedreturn# 二叉樹遍歷框架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 clonedreturn 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 Falseif root.left is None and root.right is None:# 到達葉子結點，判斷是否同時到達數組末端return arr[i] == root.val and i == len(arr) - 1if 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 = arrself.traverse(root)return self.isValid# 記錄遍歷深度（函數的索引）def __init__(self):self.d = 0self.arr = []self.isValid = False# 二叉樹遍歷函數def traverse(self, root: TreeNode):if root is None or self.isValid:returnif 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 = Truereturnif self.d >= len(self.arr) or self.arr[self.d] != root.val:returnself.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# 拷貝節點，存到 nodeToCopycpRoot = 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