leetcode二叉樹3

404.左葉子之和

給定二叉樹的根節點?root?，返回所有左葉子之和。

示例 1：
輸入: root = [3,9,20,null,null,15,7] 
輸出: 24 
解釋: 在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24
示例?2:
輸入: root = [1]
輸出: 0
提示:

節點數在?[1, 1000]?范圍內
-1000 <= Node.val <= 1000

解題思路

通過遞歸遍歷二叉樹，識別并累加所有左葉子節點的值。使用一個標志變量 flag 區分當前節點是否為其父節點的左子節點，只有當節點是葉子節點且是左子節點時，才將其值加到全局變量 sum 中。主函數從根節點開始遞歸，特殊處理單節點樹（根節點不算左葉子），最終返回總和。

代碼?

class Solution {int sum = 0; // 定義全局變量，用于累加所有左葉子節點的值// 輔助函數：遞歸遍歷二叉樹，計算左葉子之和// root: 當前處理的節點// flag: 標記當前節點是左子節點(1)還是右子節點(0)public void fun1(TreeNode root, int flag) {// 如果當前節點是葉子節點（無左子節點且無右子節點）if (root.left == null && root.right == null) { // 檢查是否是左葉子節點，只有 flag 為 1 時才累加if (flag == 1) {sum += root.val; // 將左葉子節點的值加到 sum 中}} else { // 如果不是葉子節點，繼續遞歸處理子節點// 如果存在左子節點，遞歸調用并標記為左子節點 (flag=1)if (root.left != null) fun1(root.left, 1);// 如果存在右子節點，遞歸調用并標記為右子節點 (flag=0)if (root.right != null) fun1(root.right, 0);}}// 主函數：返回二叉樹所有左葉子之和public int sumOfLeftLeaves(TreeNode root) {// 特殊情況：如果樹只有一個節點（根節點是葉子），返回 0if (root.left == null && root.right == null) {return 0; // 根節點本身不算左葉子}fun1(root, 0); // 從根節點開始遞歸，根節點初始標記為 0（非左子節點）return sum; // 返回累加的結果}
}

513.找樹左下角的值

給定一個二叉樹的?根節點?root，請找出該二叉樹的?最底層?最左邊?節點的值。

假設二叉樹中至少有一個節點。

示例 1:
輸入: root = [2,1,3]
輸出: 1
示例 2:
輸入: [1,2,3,4,null,5,6,null,null,7]
輸出: 7
提示:

二叉樹的節點個數的范圍是?[1,104]
-231?<= Node.val <= 231?- 1?

?

解題思路

通過層次遍歷（BFS，廣度優先搜索）找到二叉樹的最底層，并記錄每一層的最左節點值。由于層次遍歷從左到右訪問節點，每層的第一個節點即為最左節點，而最后一層的第一個節點即為最底層的最左節點。使用隊列存儲每層節點，遍歷完所有層后，ans 保存的就是目標值。

代碼?

class Solution {public int findBottomLeftValue(TreeNode root) {int ans = root.val; // 初始化答案為根節點的值，作為最底層最左節點的候選Queue<TreeNode> queue = new ArrayDeque<>(); // 創建隊列，用于層次遍歷queue.offer(root); // 將根節點加入隊列，開始遍歷// 當隊列不為空時，繼續層次遍歷while (!queue.isEmpty()) {boolean flag = true; // 標志位，用于標記每層的最左節點int size = queue.size(); // 獲取當前層的節點數// 遍歷當前層的所有節點while (size-- > 0) {TreeNode node = new TreeNode(); // 創建一個臨時節點對象（稍顯冗余）node = queue.poll(); // 從隊列中取出當前節點，覆蓋臨時對象if (flag) ans = node.val; // 如果是該層第一個節點，更新答案為當前節點值flag = false; // 標志位置為 false，確保只記錄最左節點// 將左子節點加入隊列（如果存在）if (node.left != null) queue.offer(node.left);// 將右子節點加入隊列（如果存在）if (node.right != null) queue.offer(node.right);}}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
解釋：由于樹是空的，所以不存在根節點到葉子節點的路徑。
提示：

樹中節點的數目在范圍?[0, 5000]?內
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解題思路

通過深度優先搜索（DFS）遞歸遍歷二叉樹，從根節點到每個葉子節點計算路徑和。每次遞歸時累加當前節點值，并在到達葉子節點時檢查路徑和是否等于目標值 targetSum。如果存在至少一條路徑滿足條件，則返回 true，否則返回 false。主函數處理空樹情況，并啟動遞歸過程。

代碼?

class Solution {// 輔助函數：遞歸檢查是否存在從當前節點到葉子節點的路徑和等于目標值// root: 當前處理的節點// sum: 從根節點到當前節點的路徑和// targetSum: 目標和public boolean fun1(TreeNode root, int sum, int targetSum) {// 如果當前節點為空，返回 false（空路徑不滿足條件）if (root == null) {return false;}// 將當前節點值加到路徑和中sum += root.val;// 如果當前節點是葉子節點（無左子節點且無右子節點）if (root.left == null && root.right == null) {// 檢查路徑和是否等于目標和，若相等返回 trueif (sum == targetSum) return true;}// 遞歸檢查左子樹或右子樹是否存在滿足條件的路徑// 使用 || 表示只要有一條路徑滿足條件即返回 truereturn fun1(root.left, sum, targetSum) || fun1(root.right, sum, targetSum);}// 主函數：判斷是否存在從根節點到葉子節點的路徑和等于目標值public boolean hasPathSum(TreeNode root, int targetSum) {// 特殊情況：如果樹為空，返回 falseif (root == null) {return false;}// 調用輔助函數，從根節點開始，初始路徑和為 0return fun1(root, 0, targetSum);}
}

113.路徑總和II

給你二叉樹的根節點?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

解題思路

通過深度優先搜索（DFS）遞歸遍歷二叉樹，從根節點到每個葉子節點，記錄路徑并計算路徑和。使用一個臨時列表 list 保存當前路徑，在到達葉子節點時檢查路徑和是否等于目標值 targetSum，若滿足則將路徑副本加入結果集 ans。通過回溯（移除當前節點值）確保路徑記錄的正確性，最終返回所有滿足條件的路徑。

代碼?

class Solution {// 定義全局變量，用于存儲所有滿足條件的路徑List<List<Integer>> ans = new ArrayList<>();// 輔助函數：遞歸遍歷二叉樹，尋找從根到葉子路徑和等于目標值的路徑// root: 當前處理的節點// sum: 從根節點到當前節點的路徑和// targetSum: 目標和// list: 當前路徑的臨時記錄public void fun1(TreeNode root, int sum, int targetSum, ArrayList list) {// 如果當前節點為空，直接返回（空路徑不處理）if (root == null) {return;}// 將當前節點值加入臨時路徑list.add(root.val);// 更新路徑和sum += root.val;// 如果當前節點是葉子節點（無左子節點且無右子節點）if (root.left == null && root.right == null) {// 檢查路徑和是否等于目標和if (sum == targetSum) {// 如果滿足條件，將當前路徑的副本加入結果集ans.add(new ArrayList<>(list));}} else {// 如果不是葉子節點，繼續遞歸遍歷左子樹fun1(root.left, sum, targetSum, list);// 遞歸遍歷右子樹fun1(root.right, sum, targetSum, list);}// 回溯：移除當前節點值，以便嘗試其他路徑list.remove(list.size() - 1);}// 主函數：返回所有從根到葉子路徑和等于目標值的路徑public List<List<Integer>> pathSum(TreeNode root, int targetSum) {// 創建臨時列表，用于記錄當前路徑ArrayList<Integer> list = new ArrayList<>();// 調用輔助函數開始遞歸fun1(root, 0, targetSum, list);// 返回結果集return ans;}
}

106.從中序與后序遍歷構造二叉樹

給定兩個整數數組?inorder?和?postorder?，其中?inorder?是二叉樹的中序遍歷，?postorder?是同一棵樹的后序遍歷，請你構造并返回這顆?二叉樹?。

示例 1:
輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]
示例 2:
輸入：inorder = [-1], postorder = [-1]
輸出：[-1]
提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder?和?postorder?都由?不同?的值組成
postorder?中每一個值都在?inorder?中
inorder?保證是樹的中序遍歷
postorder?保證是樹的后序遍歷

解題思路

利用后序遍歷的最后一個元素作為根節點，通過中序遍歷找到根節點的左右子樹范圍，遞歸構建二叉樹。為了避免每次線性查找根節點在中序遍歷中的位置，使用哈希表預先存儲值到索引的映射，從而將查找時間從 O(n) 優化到 O(1)。通過遞歸劃分數組范圍，最終構造出完整的二叉樹。

代碼

class Solution {// 定義哈希表，用于快速查找中序遍歷中值的索引private HashMap<Integer, Integer> inorderMap;// 輔助函數：根據中序和后序遍歷遞歸構建二叉樹// inorder: 中序遍歷數組// postorder: 后序遍歷數組// inStart, inEnd: 中序遍歷的當前范圍// postStart, postEnd: 后序遍歷的當前范圍private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {// 如果當前范圍無效，返回 null（無子樹）if (inStart > inEnd) {return null;}// 后序遍歷的最后一個元素是當前子樹的根節點int rootVal = postorder[postEnd];TreeNode root = new TreeNode(rootVal);// 在中序遍歷中找到根節點的索引int rootIndex = inorderMap.get(rootVal);// 計算左子樹的節點數int leftSize = rootIndex - inStart;// 遞歸構建左子樹root.left = buildTreeHelper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1);// 遞歸構建右子樹root.right = buildTreeHelper(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);return root;}// 主函數：根據中序和后序遍歷構造二叉樹public TreeNode buildTree(int[] inorder, int[] postorder) {// 初始化哈希表，存儲中序遍歷值到索引的映射inorderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inorderMap.put(inorder[i], i);}// 調用輔助函數，初始范圍為整個數組return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);}
}// TreeNode 定義（假設已提供）
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}

105.從前序與中序遍歷序列構造二叉樹

給定兩個整數數組?preorder?和?inorder?，其中?preorder?是二叉樹的先序遍歷，?inorder?是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

示例 1:
輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]
示例 2:
輸入: preorder = [-1], inorder = [-1]
輸出: [-1]
提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder?和?inorder?均?無重復?元素
inorder?均出現在?preorder
preorder?保證?為二叉樹的前序遍歷序列
inorder?保證?為二叉樹的中序遍歷序列

?

解題思路

利用前序遍歷的第一個元素作為根節點，通過中序遍歷找到根節點的左右子樹范圍，遞歸構建二叉樹。為了避免每次線性查找根節點在中序遍歷中的位置，使用哈希表預先存儲值到索引的映射，從而將查找時間從 O(n) 優化到 O(1)。通過遞歸劃分數組范圍，最終構造出完整的二叉樹。

代碼?

class Solution {// 定義哈希表，用于快速查找中序遍歷中值的索引private HashMap<Integer, Integer> inorderMap;// 輔助函數：根據前序和中序遍歷遞歸構建二叉樹// inorder: 中序遍歷數組// preorder: 前序遍歷數組// inStart, inEnd: 中序遍歷的當前范圍// preStart, preEnd: 前序遍歷的當前范圍public TreeNode fun1(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd) {// 如果當前范圍無效（中序或前序范圍不合法），返回 nullif (inEnd < inStart || preStart > preEnd) return null;// 前序遍歷的第一個元素是當前子樹的根節點TreeNode root = new TreeNode(preorder[preStart]);// 在中序遍歷中找到根節點的索引（使用哈希表快速查找）int mid = inorderMap.get(root.val);// 計算左子樹的節點數int leftSize = mid - inStart;// 遞歸構建左子樹// 左子樹的中序范圍: [inStart, mid - 1]// 左子樹的前序范圍: [preStart + 1, preStart + leftSize]root.left = fun1(inorder, preorder, inStart, mid - 1, preStart + 1, preStart + leftSize);// 遞歸構建右子樹// 右子樹的中序范圍: [mid + 1, inEnd]// 右子樹的前序范圍: [preStart + leftSize + 1, preEnd]root.right = fun1(inorder, preorder, mid + 1, inEnd, preStart + leftSize + 1, preEnd);// 返回當前子樹的根節點return root;}// 主函數：根據前序和中序遍歷構造二叉樹public TreeNode buildTree(int[] preorder, int[] inorder) {// 如果輸入數組為空或長度為 0，返回 nullif (inorder == null || inorder.length == 0) return null;// 初始化哈希表，存儲中序遍歷值到索引的映射inorderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inorderMap.put(inorder[i], i);}// 調用輔助函數，初始范圍為整個數組return fun1(inorder, preorder, 0, inorder.length - 1, 0, preorder.length - 1);}
}// TreeNode 定義（假設已提供）
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}

?654.最大二叉樹

給定一個不重復的整數數組?nums?。?最大二叉樹?可以用下面的算法從?nums?遞歸地構建:

創建一個根節點，其值為?nums?中的最大值。
遞歸地在最大值?左邊?的?子數組前綴上?構建左子樹。
遞歸地在最大值?右邊?的?子數組后綴上?構建右子樹。

返回?nums?構建的?最大二叉樹?。

示例 1：
輸入：nums = [3,2,1,6,0,5]
輸出：[6,3,5,null,2,0,null,null,1]
解釋：遞歸調用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左邊部分是 [3,2,1] ，右邊部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ，左邊部分是 [] ，右邊部分是 [2,1] 。- 空數組，無子節點。- [2,1] 中的最大值是 2 ，左邊部分是 [] ，右邊部分是 [1] 。- 空數組，無子節點。- 只有一個元素，所以子節點是一個值為 1 的節點。- [0,5] 中的最大值是 5 ，左邊部分是 [0] ，右邊部分是 [] 。- 只有一個元素，所以子節點是一個值為 0 的節點。- 空數組，無子節點。
示例 2：
輸入：nums = [3,2,1]
輸出：[3,null,2,null,1]
提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums?中的所有整數?互不相同

解題思路

通過遞歸分治的方式構建最大二叉樹。每次在當前子數組范圍內找到最大值作為根節點，然后將數組分為左子數組和右子數組，分別遞歸構建左子樹和右子樹。使用索引范圍控制遞歸，確保正確劃分子樹，最終返回構造好的二叉樹根節點。

代碼?

class Solution {// 輔助函數：遞歸構建最大二叉樹// nums: 輸入的整數數組// start: 當前子數組的起始索引// end: 當前子數組的結束索引public TreeNode fun1(int[] nums, int start, int end) {// 如果當前范圍無效（起始索引大于結束索引），返回 nullif (start > end) return null;// 創建當前子樹的根節點TreeNode root = new TreeNode();int max = 0;    // 記錄當前范圍內的最大值int index = 0;  // 記錄最大值的索引// 遍歷當前范圍，找到最大值及其索引for (int i = start; i <= end; i++) {if (max <= nums[i]) { // 使用 <= 確保更新到最后一個最大值index = i;        // 更新最大值索引max = nums[i];    // 更新最大值}}// 設置根節點值為最大值root.val = max;// 遞歸構建左子樹（最大值左邊的子數組）root.left = fun1(nums, start, index - 1);// 遞歸構建右子樹（最大值右邊的子數組）root.right = fun1(nums, index + 1, end);// 返回當前子樹的根節點return root;}// 主函數：根據數組構造最大二叉樹public TreeNode constructMaximumBinaryTree(int[] nums) {// 特殊情況：如果數組長度為 1，直接返回單節點樹if (nums.length == 1) return new TreeNode(nums[0]);// 調用輔助函數，初始范圍為整個數組return fun1(nums, 0, nums.length - 1);}
}