LeetCode 算法題解：鏈表與二叉樹相關問題

在算法學習和實踐中，LeetCode 是一個非常好的平臺，它包含了各種各樣的算法題目，有助于我們提升編程能力和解決問題的能力。本文將詳細講解在 leetcoding.cpp 文件中實現的一些鏈表和二叉樹相關的算法題。

一、鏈表相關問題

1. 鏈表的中間節點

題目要求：給你單鏈表的頭結點 head，找出并返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。

ListNode *middleNode(ListNode *head)
{ListNode *slow = head;ListNode *fast = head;if (head == nullptr || head->next == nullptr){return nullptr;}while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

思路：使用快慢指針的方法。快指針 fast 每次移動兩步，慢指針 slow 每次移動一步。當快指針到達鏈表末尾時，慢指針正好指向鏈表的中間節點。

2. 二進制鏈表轉十進制

題目要求：給定一個單鏈表，鏈表中每個結點的值不是 0 就是 1，此鏈表是一個整數數字的二進制表示形式，返回該鏈表所表示數字的十進制值。

int getDecimalValue(ListNode *head)
{if (head == nullptr || head->next == nullptr){return head->val;}int length = 0;ListNode *cur = head;while (cur){length++;cur = cur->next;}int bit = length - 1;int res = 0;while (head){res += head->val * pow(2, bit);bit--;head = head->next;}return res;
}

思路：首先遍歷鏈表得到鏈表的長度，從而確定每個節點對應的二進制位。然后再次遍歷鏈表，根據每個節點的值和對應的二進制位計算十進制值。

3. 鏈表相交節點

題目要求：找到兩個單鏈表相交的起始節點。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{ListNode *curA = headA;ListNode *curB = headB;while (curA != curB){curA = curA == nullptr ? headB : curA->next;curB = curB == nullptr ? headA : curB->next;if (curA == nullptr){curA = headB;}if (curB == nullptr){curB = headA;}}return curA;
}

思路：讓兩個指針分別從兩個鏈表的頭節點開始遍歷，當一個指針到達鏈表末尾時，將其指向另一個鏈表的頭節點。這樣，兩個指針走過的總路程相等，最終會在相交節點相遇。

4. 鏈表倒數第 k 個節點

題目要求：找出單向鏈表中倒數第 k 個節點，并返回該節點的值。

int kthToLast(ListNode *head, int k)
{if (head == nullptr){return -1;}ListNode *cur = head;int length = 0;while (cur){length++;cur = cur->next;}if (k < 1 || k > length){return -1;}cur = head;int count = 0;while (cur){count++;if (count == length - k + 1){int key_value = cur->val;return key_value;}cur = cur->next;}return -1;
}

思路：先遍歷鏈表得到鏈表的長度，然后根據長度和 k 的值計算出倒數第 k 個節點是正數第幾個節點，最后再次遍歷鏈表找到該節點。

二、二叉樹相關問題

1. 將有序數組轉換為平衡二叉搜索樹

題目要求：將一個按升序排列的整數數組轉換為一棵平衡二叉搜索樹。

TreeNode *buildBST(vector<int> &nums, int left, int right)
{if (left > right){return nullptr;}int mid = left + (right - left) / 2;TreeNode *root = new TreeNode(nums[mid]);root->left = buildBST(nums, left, mid - 1);root->right = buildBST(nums, mid + 1, right);return root;
}TreeNode *sortedArrayToBST(vector<int> &nums)
{return buildBST(nums, 0, nums.size() - 1);
}

思路：使用遞歸的方法，每次選擇數組的中間元素作為根節點，然后遞歸地構建左子樹和右子樹。

2. 二叉樹的最小深度

題目要求：找出二叉樹的最小深度，即從根節點到最近葉子節點的最短路徑上的節點數量。

int minDepth(TreeNode *root)
{if (root == nullptr){return 0;}if (root->left == nullptr && root->right == nullptr){return 1;}if (root->left == nullptr){return minDepth(root->right) + 1;}if (root->right == nullptr){return minDepth(root->left) + 1;}return min(minDepth(root->left), minDepth(root->right)) + 1;
}

思路：使用遞歸的方法，分別計算左子樹和右子樹的最小深度，然后取較小值加 1 作為當前節點的最小深度。

3. 翻轉二叉樹

題目要求：翻轉一棵二叉樹，即調換左右子樹的位置。

TreeNode *invertTree(TreeNode *root)
{if (root == nullptr){return nullptr;}TreeNode *tmp = nullptr;tmp = root->left;root->left = root->right;root->right = tmp;invertTree(root->left);invertTree(root->right);return root;
}

思路：使用遞歸的方法，先交換當前節點的左右子樹，然后遞歸地翻轉左子樹和右子樹。

4. 二叉樹的所有路徑

題目要求：返回二叉樹中所有從根節點到葉子節點的路徑。

vector<string> binaryTreePaths(TreeNode *root)
{vector<string> res = {};if (root == nullptr){return res;}if (root->left == nullptr && root->right == nullptr){res.push_back(to_string(root->val));return res;}vector<string> leftPaths = binaryTreePaths(root->left);for (string &path : leftPaths){res.push_back(to_string(root->val) + "->" + path);}vector<string> rightPaths = binaryTreePaths(root->right);for (string &path : rightPaths){res.push_back(to_string(root->val) + "->" + path);}return res;
}

思路：使用遞歸的方法，分別遞歸地獲取左子樹和右子樹的所有路徑，然后將當前節點的值添加到這些路徑的前面。

5. 左葉子之和

題目要求：計算二叉樹中所有左葉子節點的值之和。

int sumOfLeftLeaves(TreeNode *root)
{if (root == nullptr)return 0;int sum = 0;if (root->left && root->left->left == nullptr && root->left->right == nullptr){sum += root->left->val;}sum += sumOfLeftLeaves(root->left);sum += sumOfLeftLeaves(root->right);return sum;
}

思路：使用遞歸的方法，判斷當前節點的左子節點是否為左葉子節點，如果是則將其值加入總和，然后遞歸地計算左子樹和右子樹的左葉子節點之和。

6. 二叉樹的直徑

題目要求：計算二叉樹中任意兩個節點之間最長路徑的長度，這條路徑可能經過也可能不經過根節點。

int max_diameter = 0;int dfs(TreeNode *root)
{if (root == nullptr)return 0;int l = dfs(root->left);int r = dfs(root->right);max_diameter = max(max_diameter, l + r);return max(l, r) + 1;
}int diameterOfBinaryTree(TreeNode *root)
{max_diameter = 0;dfs(root);return max_diameter;
}

思路：使用深度優先搜索（DFS）的方法，遞歸地計算每個節點的左右子樹的深度，然后更新最大直徑。

7. 二叉樹的坡度

題目要求：計算并返回整個二叉樹的坡度，一個節點的坡度定義為該節點左子樹的節點之和和右子樹節點之和的差的絕對值，整個樹的坡度就是其所有節點的坡度之和。

int total_tilt = 0;
int dfs1(TreeNode *node)
{if (node == nullptr){return 0;}int left_sum = 0;int right_sum = 0;left_sum += dfs1(node->left);right_sum = dfs1(node->right);total_tilt += abs(left_sum - right_sum);return left_sum + right_sum + node->val;
}int findTilt(TreeNode *root)
{dfs1(root);return total_tilt;
}

思路：使用遞歸的方法，計算每個節點的左右子樹的節點之和，然后計算該節點的坡度并累加到總坡度中。

8. 子樹判斷

題目要求：檢驗一棵二叉樹中是否包含和另一棵二叉樹具有相同結構和節點值的子樹。

bool isSameTree(TreeNode *root, TreeNode *subRoot)
{if (root == nullptr && subRoot == nullptr){return true;}if (root == nullptr || subRoot == nullptr){return false;}return root->val == subRoot->val && isSameTree(root->left, subRoot->left) && isSameTree(root->right, subRoot->right);
}bool isSubtree(TreeNode *root, TreeNode *subRoot)
{if (root == nullptr && subRoot == nullptr){return true;}if (root == nullptr || subRoot == nullptr){return false;}if (root->val == subRoot->val){if (isSameTree(root, subRoot)){return true;}}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

思路：先定義一個輔助函數 isSameTree 用于判斷兩棵樹是否相同，然后遞歸地在主樹的每個節點上調用該函數，判斷是否存在與子樹相同的子樹。

9. 合并二叉樹

題目要求：將兩棵二叉樹合并成一棵新二叉樹，如果兩個節點重疊，則將這兩個節點的值相加作為合并后節點的新值；否則，不為 null 的節點將直接作為新二叉樹的節點。

TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2)
{if (root1 == nullptr)return root2;if (root2 == nullptr)return root1;TreeNode *root = new TreeNode(root1->val + root2->val);root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;
}

思路：使用遞歸的方法，合并當前節點的值，然后遞歸地合并左子樹和右子樹。

10. 二叉樹每層節點的平均值

題目要求：返回二叉樹每一層節點的平均值。

vector<double> averageOfLevels(TreeNode *root)
{queue<TreeNode *> q;vector<double> res;double avarage_number = 0;if (!root){return res;}q.push(root);while (!q.empty()){int size = q.size();double sum = 0;for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();sum += node->val;if (node->left)q.push(node->left);if (node->right)q.push(node->right);}avarage_number = sum / size;res.push_back(avarage_number);}return res;
}

思路：使用層序遍歷的方法，遍歷每一層的節點，計算該層節點的總和，然后除以節點數量得到平均值。

11. 二叉搜索樹中是否存在兩數之和等于目標值

題目要求：判斷二叉搜索樹中是否存在兩個元素，它們的和等于給定的目標結果。

vector<int> nums;void find_dfs(TreeNode *node)
{if (node == nullptr){return;}find_dfs(node->left);nums.push_back(node->val);find_dfs(node->right);
}bool findTarget(TreeNode *root, int k)
{find_dfs(root);int i = 0, j = nums.size() - 1;while (i < j){int sum = nums[i] + nums[j];if (sum == k){return true;}else if (sum < k){i++;}else{j--;}}return false;
}

思路：先使用中序遍歷將二叉搜索樹的節點值存儲在一個數組中，然后使用雙指針法在數組中查找是否存在兩數之和等于目標值。

12. 二叉樹中第二小的值

題目要求：找出二叉樹中所有節點中的第二小的值，如果不存在則返回 -1。

vector<int> nums;void dfs_find_min(TreeNode *node)
{if (node == nullptr){return;}dfs_find_min(node->left);nums.push_back(node->val);dfs_find_min(node->right);
}int findSecondMinimumValue(TreeNode *root)
{nums.clear();if (root == nullptr){return -1;}dfs_find_min(root);if (nums.empty())return -1;int min1 = nums[0];int i = 1;while (i < nums.size() && nums[i] == min1)i++;if (i == nums.size())return -1;return nums[i];
}

思路：使用中序遍歷將二叉樹的節點值存儲在一個數組中，然后遍歷數組找到第二小的值。

13. 二叉搜索樹的搜索

題目要求：在二叉搜索樹中找到節點值等于給定值的節點，并返回以該節點為根的子樹，如果節點不存在則返回 null。

TreeNode *searchBST(TreeNode *root, int val)
{if (root == nullptr)return nullptr;if (root->val == val)return root;if (val < root->val)return searchBST(root->left, val);elsereturn searchBST(root->right, val);
}

思路：利用二叉搜索樹的性質，左子樹的節點值小于根節點，右子樹的節點值大于根節點，遞歸地搜索目標節點。

14. 二叉搜索樹中任意兩不同節點值之間的最小差值

題目要求：返回二叉搜索樹中任意兩不同節點值之間的最小差值。

vector<int> inorder_nums;void inorder(TreeNode *root)
{if (root == nullptr)return;inorder(root->left);nums.push_back(root->val);inorder(root->right);
}int getMinimumDifference(TreeNode *root)
{inorder(root);int res = INT_MAX;for (int i = 1; i < nums.size(); i++){res = min(res, nums[i] - nums[i - 1]);}return res;
}

思路：使用中序遍歷將二叉搜索樹的節點值存儲在一個數組中，由于中序遍歷的結果是有序的，所以最小差值一定出現在相鄰的兩個節點之間，遍歷數組計算相鄰節點的差值并取最小值。

15. 葉子相似的二叉樹

題目要求：判斷兩棵二叉樹的葉子節點值按從左到右的順序排列是否相同。

void getLeaves(TreeNode *root, vector<int> &leaves)
{if (!root)return;if (!root->left && !root->right){leaves.push_back(root->val);return;}getLeaves(root->left, leaves);getLeaves(root->right, leaves);
}bool leafSimilar(TreeNode *root1, TreeNode *root2)
{vector<int> leaves1, leaves2;getLeaves(root1, leaves1);getLeaves(root2, leaves2);return leaves1 == leaves2;
}

思路：分別遍歷兩棵二叉樹，將它們的葉子節點值存儲在兩個數組中，然后比較這兩個數組是否相同。

16. 將二叉搜索樹轉換為遞增順序搜索樹

題目要求：將一棵二叉搜索樹按中序遍歷重新排列為一棵遞增順序搜索樹，使樹中最左邊的節點成為樹的根節點，并且每個節點沒有左子節點，只有一個右子節點。

vector<TreeNode *> nums_node;void dfs_inor(TreeNode *node)
{if (node == nullptr){return;}dfs_inor(node->left);nums_node.push_back(node);dfs_inor(node->right);
}TreeNode *increasingBST(TreeNode *root)
{if (root == nullptr){return nullptr;}nums_node.clear();dfs_inor(root);TreeNode *node = nums_node[0];for (int i = 0; i < nums_node.size() - 1; i++){nums_node[i]->left = nullptr;nums_node[i]->right = nums_node[i + 1];}nums_node.back()->left = nullptr;nums_node.back()->right = nullptr;return node;
}

思路：使用中序遍歷將二叉搜索樹的節點存儲在一個數組中，然后重新連接這些節點，使其成為一棵遞增順序搜索樹。

17. 二叉搜索樹中值位于指定范圍內的節點值之和

題目要求：返回二叉搜索樹中值位于范圍 [low, high] 之間的所有結點的值的和。

int rangeSumBST(TreeNode *root, int low, int high)
{if (root == nullptr){return 0;}nums_node.clear();inorder(root);int sum = 0;for (auto i : nums_node){if ((i->val >= low) && (i->val <= high)){sum += i->val;}}return sum;
}

思路：使用中序遍歷將二叉搜索樹的節點存儲在一個數組中，然后遍歷數組，將值位于指定范圍內的節點值相加。

18. 判斷二叉樹是否為單值二叉樹

題目要求：判斷一棵二叉樹是否每個節點都具有相同的值，如果是則返回 true，否則返回 false。

bool isUnivalTree(TreeNode *root)
{if (!root)return true;if (root->left && root->left->val != root->val)return false;if (root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

思路：使用遞歸的方法，判斷當前節點的左右子節點的值是否與當前節點的值相同，如果不同則返回 false，否則遞歸地判斷左子樹和右子樹。

19. 判斷二叉樹中兩個節點是否為堂兄弟節點

題目要求：判斷二叉樹中兩個不同節點的值 x 和 y 對應的節點是否為堂兄弟節點，即深度相同但父節點不同。

TreeNode *x_parent = nullptr;
TreeNode *y_parent = nullptr;
int x_depth = -1;
int y_depth = -1;void dfs(TreeNode *node, TreeNode *parent, int depth, int x, int y)
{if (!node)return;if (node->val == x){x_parent = parent;x_depth = depth;}if (node->val == y){y_parent = parent;y_depth = depth;}dfs(node->left, node, depth + 1, x, y);dfs(node->right, node, depth + 1, x, y);
}bool isCousins(TreeNode *root, int x, int y)
{x_parent = y_parent = nullptr;x_depth = y_depth = -1;dfs(root, nullptr, 0, x, y);return x_depth == y_depth && x_parent != y_parent;
}

思路：使用深度優先搜索（DFS）的方法，記錄節點 x 和 y 的父節點和深度，最后判斷它們的深度是否相同且父節點是否不同。

20. 二叉樹從根到葉路徑表示的數字之和

題目要求：計算二叉樹中從根到葉路徑所表示的數字之和，每條路徑表示一個從最高有效位開始的二進制數。

int sumRootToLeaf(TreeNode *root)
{if (root == nullptr){return 0;}vector<vector<int>> paths;vector<int> currentPath;dfs(root, currentPath, paths);int sum = 0;for (const auto &path : paths){int num = 0;for (int val : path){num = num * 2 + val;num %= 1000000007;}sum += num;sum %= 1000000007;}return sum;
}private:
void dfs(TreeNode *node, vector<int> &currentPath, vector<vector<int>> &paths)
{if (node == nullptr){return;}currentPath.push_back(node->val);if (node->left == nullptr && node->right == nullptr){paths.push_back(currentPath);}dfs(node->left, currentPath, paths);dfs(node->right, currentPath, paths);currentPath.pop_back();
}

思路：使用深度優先搜索（DFS）的方法，記錄所有從根到葉的路徑，然后將每條路徑表示的二進制數轉換為十進制數并求和。

總結

通過對這些鏈表和二叉樹相關的算法題的講解，我們可以看到遞歸、雙指針、深度優先搜索、層序遍歷等算法思想在解決問題中的重要性。在實際編程中，我們需要根據問題的特點選擇合適的算法思想和數據結構，以提高算法的效率和性能。希望這些題解能夠幫助大家更好地理解和掌握算法知識。

完成代碼

#include <functional>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <tuple>
#include <queue>
using namespace std;/*** 繼續刷一些leetcode的題目**//*** 關與鏈表的中間節點* 給你單鏈表的頭結點 head ，請你找出并返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。*///   Definition for singly-linked list.
struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:/*** 返回中間節點的值*/ListNode *middleNode(ListNode *head){ListNode *slow = head;ListNode *fast = head;if (head == nullptr || head->next == nullptr){return nullptr;}while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}/*** 給你一個單鏈表的引用結點 head。鏈表中每個結點的值不是 0 就是 1。已知此鏈表是一個整數數字的二進制表示形式。請你返回該鏈表所表示數字的 十進制值*/int getDecimalValue(ListNode *head){/*** 輸入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]輸出：18880*/if (head == nullptr || head->next == nullptr){return head->val;}int length = 0;ListNode *cur = head;while (cur){length++;cur = cur->next;}// 得到鏈表的長度int bit = length - 1;int res = 0;while (head){res += head->val * pow(2, bit);bit--;head = head->next;}/*** 核心代碼解釋：* . 逐步解釋① res += head->val * pow(2, bit);pow(2, bit) 計算當前位的權值（2 的 bit 次方）。head->val * pow(2, bit) 得到當前節點的十進制值。把這個值加到 res 上，實現累加。② bit--;處理完當前節點后，下一位的權值要減 1（向右移動一位，權值減半）。③ head = head->next;指針后移，處理下一個節點。*/return res;}/*** 輸入：nums = [1,2,3,4,5]輸出：[5,4,3,2,1]*/ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){ListNode *curA = headA;ListNode *curB = headB;while (curA != curB){curA = curA == nullptr ? headB : curA->next;curB = curB == nullptr ? headA : curB->next;if (curA == nullptr){curA = headB;}if (curB == nullptr){curB = headA;}}return curA; // 或者 curB，二者相等}/*** 簡單相關標簽premium lock icon相關企業提示實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該節點的值。注意：本題相對原題稍作改動示例：輸入： 1->2->3->4->5 和 k = 2輸出： 4
說明：*/int kthToLast(ListNode *head, int k){if (head == nullptr){return -1; // 空鏈表}ListNode *cur = head;int length = 0;while (cur){length++;cur = cur->next;}/*得到鏈表的長度*/if (k < 1 || k > length){return -1; // k值無效}cur = head; // 重置cur指針int count = 0;while (cur){count++;if (count == length - k + 1){int key_value = cur->val;return key_value;}cur = cur->next;}return -1; // 找不到指定節點}}
};/*** 實現一個經典的二叉樹的方法* 以及二叉樹的相關題目合集*/
//  Definition for a binary tree node.
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution
{
public:/*** 給你一個整數數組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 平衡 二叉搜索樹。*/TreeNode *buildBST(vector<int> &nums, int left, int right){if (left > right){return nullptr; // 基本情況：如果左邊界大于右邊界，返回空}int mid = left + (right - left) / 2;      // 找到中間元素TreeNode *root = new TreeNode(nums[mid]); // 創建根節點// 遞歸構建左子樹和右子樹root->left = buildBST(nums, left, mid - 1);root->right = buildBST(nums, mid + 1, right);return root; // 返回構建好的樹}TreeNode *sortedArrayToBST(vector<int> &nums){// 實現數組轉化為平衡二叉搜索樹return buildBST(nums, 0, nums.size() - 1);}/*** 靈魂的孤獨與彷徨* 矢志不渝的堅守自我的道路* 而今多少事  都付笑談中* 給定一個二叉樹，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。說明：葉子節點是指沒有子節點的節點。*/int minDepth(TreeNode *root){/**返回樹的最小 深度 */if (root == nullptr){return 0;}// 還有一些其他的情況if (root->left == nullptr && root->right == nullptr){return 1; // 如果是葉子節點}if (root->left == nullptr){return minDepth(root->right) + 1;}if (root->right == nullptr){return minDepth(root->left) + 1;}return min(minDepth(root->left), minDepth(root->right)) + 1;}int min_depth(TreeNode *root){/*使用BFS（層序遍歷）求最小深度*/if (root == nullptr)return 0;queue<TreeNode *> q;q.push(root);int depth = 0;while (!q.empty()){int size = q.size();depth++;for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();// 如果遇到第一個葉子節點，直接返回當前深度if (node->left == nullptr && node->right == nullptr){return depth;}if (node->left != nullptr){q.push(node->left);}if (node->right != nullptr){q.push(node->right);}}}return depth;}/*** 還是應該褪去過去的泥濘* 繼續繼續  沒有只升不降的波浪  沒有跨不過去的門欄*//*** 給你一棵二叉樹的根節點 root ，翻轉這棵二叉樹，并返回其根節點。*/TreeNode *invertTree(TreeNode *root){// 如何翻轉二叉樹/*** 所謂翻轉就是調換左右子樹的位置* 使用遞歸的方式*/if (root == nullptr){return nullptr;}TreeNode *tmp = nullptr;tmp = root->left;         // 先保存左子樹root->left = root->right; // 將右子樹賦值給左子樹root->right = tmp;        // 將之前保存的左子樹賦值給右子樹invertTree(root->left);invertTree(root->right);return root;/*** 相當于交換左右節點的數值*/}/*** 給你一個二叉樹的根節點 root ，* 按 任意順序 ，* 返回所有從根節點到葉子節點的路徑。葉子節點 是指沒有子節點的節點。*/vector<string> binaryTreePaths(TreeNode *root){//  返回路徑確實是有些難度的vector<string> res = {};if (root == nullptr){return res; // 如果根節點為空，返回空路徑}// 葉子節點：直接返回包含當前節點值的路徑if (root->left == nullptr && root->right == nullptr){res.push_back(to_string(root->val));return res;}// 遞歸處理左子樹vector<string> leftPaths = binaryTreePaths(root->left);for (string &path : leftPaths){res.push_back(to_string(root->val) + "->" + path);}// 遞歸處理右子樹vector<string> rightPaths = binaryTreePaths(root->right);for (string &path : rightPaths){res.push_back(to_string(root->val) + "->" + path);}return res; // 返回結果}/*** 給定二叉樹的根節點 root ，返回所有左葉子之和。*/int sumOfLeftLeaves(TreeNode *root){if (root == nullptr)return 0;int sum = 0;if (root->left && root->left->left == nullptr && root->left->right == nullptr){sum += root->left->val;}sum += sumOfLeftLeaves(root->left);sum += sumOfLeftLeaves(root->right);return sum;}/*** 繼續前行  我就不信過不了這一關* 內心保持極致的堅定  一定沒有問題*//*** 給你一棵二叉樹的根節點，返回該樹的 直徑 。二叉樹的 直徑 是指樹中任意兩個節點之間最長路徑的 長度 。這條路徑可能經過也可能不經過根節點 root 。兩節點之間路徑的 長度 由它們之間邊數表示。*/// 在 Solution 類中添加成員變量int max_diameter = 0;/*** 深度優先遍歷* 包含前中后三序遍歷* 也就是三種遍歷方式都屬于深度優先的方式*/int dfs(TreeNode *root){if (root == nullptr)return 0;int l = dfs(root->left);int r = dfs(root->right);max_diameter = max(max_diameter, l + r); // 直徑是左右子樹深度之和return max(l, r) + 1;                    // 返回當前節點的最大深度}int diameterOfBinaryTree(TreeNode *root){max_diameter = 0; // 每次調用前重置dfs(root);return max_diameter;}/***          1/ \2   3/ \4   5dfs(1)│├─ dfs(2)│   ├─ dfs(4) → 1│   └─ dfs(5) → 1│   l=1, r=1, max_diameter=2, return 2│└─ dfs(3) → 1l=2, r=1, max_diameter=3, return 3*//*** 給你一個二叉樹的根節點 root ，計算并返回 整個樹 的坡度 。一個樹的 節點的坡度 定義即為，該節點左子樹的節點之和和右子樹節點之和的 差的絕對值 。如果沒有左子樹的話，左子樹的節點之和為 0 ；沒有右子樹的話也是一樣。空結點的坡度是 0 。整個樹 的坡度就是其所有節點的坡度之和。*/int total_tilt = 0;int dfs1(TreeNode *node){if (node == nullptr){return 0;}int left_sum = 0;int right_sum = 0;left_sum += dfs1(node->left);right_sum = dfs1(node->right);total_tilt += abs(left_sum - right_sum); // 累加當前節點的坡度return left_sum + right_sum + node->val; // 返回以當前節點為根的子樹和}int findTilt(TreeNode *root){// 找到坡度dfs1(root);return total_tilt;}/*** 給你兩棵二叉樹 root 和 subRoot 。* 檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。* 如果存在，返回 true ；否則，返回 false 。二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點。tree 也可以看做它自身的一棵子樹。*/bool isSameTree(TreeNode *root, TreeNode *subRoot){/*** 判斷是不是相同的一棵樹* 使用遞歸的方式進行判斷*/if (root == nullptr && subRoot == nullptr){return true;}if (root == nullptr || subRoot == nullptr){return false;}// 否則遞歸進行判斷return root->val == subRoot->val && isSameTree(root->left, subRoot->left) && isSameTree(root->right, subRoot->right);}bool isSubtree(TreeNode *root, TreeNode *subRoot){/*** 查看一個大樹是不是一個小樹的父親*/if (root == nullptr && subRoot == nullptr){return true;}if (root == nullptr || subRoot == nullptr){return false;}if (root->val == subRoot->val){if (isSameTree(root, subRoot)){return true;}}// 進行遞歸的比較return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);/*** 使用或者的語句* 因為* 可能左子樹相等  也可能右子樹相當*/}/*** 給你兩棵二叉樹： root1 和 root2 。想象一下，當你將其中一棵覆蓋到另一棵之上時，兩棵樹上的一些節點將會重疊（而另一些不會）。你需要將這兩棵樹合并成一棵新二叉樹。合并的規則是：如果兩個節點重疊，那么將這兩個節點的值相加作為合并后節點的新值；否則，不為 null 的節點將直接作為新二叉樹的節點。返回合并后的二叉樹。注意: 合并過程必須從兩個樹的根節點開始。*/TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2){/*** 重新寫*/if (root1 == nullptr)return root2;if (root2 == nullptr)return root1;TreeNode *root = new TreeNode(root1->val + root2->val);/*** 開創新的節點* 構造新的二叉樹結構*//*** 遞歸思想的核心* 遞歸調用精髓*/root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;}/*** 給定一個非空二叉樹的根節點 root ,*  以數組的形式返回每一層節點的平均值。* 與實際答案相差 10-5 以內的答案可以被接受。*/vector<double> averageOfLevels(TreeNode *root){/*** 返回每一層節點的平均值* 每一層：層序遍歷的方式*/// vector<double> res;//     if (!root) return res;//     queue<TreeNode*> q;//     q.push(root);//     while (!q.empty()) {//         int size = q.size();//         double sum = 0;//         for (int i = 0; i < size; i++) {//             TreeNode* node = q.front();//             q.pop();//             sum += node->val;//             if (node->left) q.push(node->left);//             if (node->right) q.push(node->right);//         }//         res.push_back(sum / size);//     }//     return res;queue<TreeNode *> q;vector<double> res;double avarage_number = 0; // 注意細節if (!root){return res;}q.push(root);while (!q.empty()){int size = q.size();double sum = 0;for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();sum += node->val;if (node->left)q.push(node->left);if (node->right)q.push(node->right);}avarage_number = sum / size;res.push_back(avarage_number);}return res;}/*** 給定一個二叉搜索樹 root 和一個目標結果 k，* 如果二叉搜索樹中存在兩個元素且它們的和等于給定的目標結果，則返回 true。*/// 兩棵樹之和vector<int> nums;void find_dfs(TreeNode *node){if (node == nullptr){return;}find_dfs(node->left);nums.push_back(node->val);find_dfs(node->right);}bool findTarget(TreeNode *root, int k){// 使用一個輔助函數find_dfs(root);int i = 0, j = nums.size() - 1;while (i < j){int sum = nums[i] + nums[j];if (sum == k){return true;}else if (sum < k){i++;}else{j--;}}return false;}/*** 給定一個非空特殊的二叉樹，每個節點都是正數，并且每個節點的子節點數量只能為 2 或 0。如果一個節點有兩個子節點的話，那么該節點的值等于兩個子節點中較小的一個。更正式地說，即 root.val = min(root.left.val, root.right.val) 總成立。給出這樣的一個二叉樹，你需要輸出所有節點中的 第二小的值 。如果第二小的值不存在的話，輸出 -1 。*/// 使用最笨的方法先試一下void dfs_find_min(TreeNode *node){if (node == nullptr){return;}dfs_find_min(node->left);nums.push_back(node->val);dfs_find_min(node->right);}int findSecondMinimumValue(TreeNode *root){nums.clear(); // 清空全局數組，防止多次調用污染if (root == nullptr){return -1;}dfs_find_min(root);if (nums.empty())return -1;int min1 = nums[0];int i = 1;// 跳過所有等于最小值的元素while (i < nums.size() && nums[i] == min1)i++;if (i == nums.size())return -1; // 沒有第二小return nums[i];}/*** 遞歸的優雅算法實現*/int find_second_min(TreeNode *root){if (!root || (!root->left && !root->right))return -1;int left = root->left->val;int right = root->right->val;if (left == root->val)left = findSecondMinimumValue(root->left);if (right == root->val)right = findSecondMinimumValue(root->right);if (left != -1 && right != -1)return min(left, right);return left != -1 ? left : right;/*** 這種思維方式比較決絕一點*/}/*** 給定二叉搜索樹（BST）的根節點 root 和一個整數值 val。你需要在 BST 中找到節點值等于 val 的節點。返回以該節點為根的子樹。 如果節點不存在，則返回 null 。*/TreeNode *searchBST(TreeNode *root, int val){if (root == nullptr)return nullptr;if (root->val == val)return root;if (val < root->val)return searchBST(root->left, val);elsereturn searchBST(root->right, val);/*** 充分利用二叉搜索樹的性質  左子樹<根<右子樹*/}/*** 給你一個二叉搜索樹的根節點 root ，返回 樹中任意兩不同節點值之間的最小差值 。差值是一個正數，其數值等于兩值之差的絕對值。*/// 補充一個中序遍歷vector<int> inorder_nums;void inorder(TreeNode *root){if (root == nullptr)return;inorder(root->left);nums.push_back(root->val);inorder(root->right);}int getMinimumDifference(TreeNode *root){// 它的要求是返回樹中任意兩不同節點值之間最小的差值inorder(root);int res = INT_MAX;for (int i = 1; i < nums.size(); i++){res = min(res, nums[i] - nums[i - 1]);/*** 這里的循環寫的很不錯啊* 循環比較前兩位的值，如果當前值比前一個值小，則更新最小差值* 然后繼續后移迭代，直到遍歷完所有節點* 前提：nums 是二叉搜索樹的中序遍歷結果，已經升序排列。思路：BST中最小差值一定出現在相鄰的兩個節點之間（因為中序遍歷有序）。循環：從第二個元素（下標1）開始，依次與前一個元素做差。用 min 函數不斷更新最小差值 res。遍歷到最后，res 就是所有相鄰節點差值中的最小值。代碼精妙之處只需比較相鄰元素，而不是所有兩兩組合，效率高，時間復雜度 O(n)。利用 BST 的有序性質，避免了多余的計算。代碼簡潔，邏輯清晰。*/}return res;}/*** 中序遍歷很重要啊* 很牛逼 從某種程度來說*//*** 請考慮一棵二叉樹上所有的葉子，這些葉子的值按從左到右的順序排列形成一個 葉值序列 。*/void getLeaves(TreeNode *root, vector<int> &leaves){if (!root)return;if (!root->left && !root->right){leaves.push_back(root->val);return;}getLeaves(root->left, leaves);getLeaves(root->right, leaves);/*** 還是對于遞歸的本質性要有深入的理解*/}bool leafSimilar(TreeNode *root1, TreeNode *root2){vector<int> leaves1, leaves2;getLeaves(root1, leaves1);getLeaves(root2, leaves2);return leaves1 == leaves2;}/*** 給你一棵二叉搜索樹的 root ，請你 按中序遍歷 將其重新排列為一棵遞增順序搜索樹，* 使樹中最左邊的節點成為樹的根節點，并且每個節點沒有左子節點，只有一個右子節點。*/vector<TreeNode *> nums_node;void dfs_inor(TreeNode *node){if (node == nullptr){return;}dfs_inor(node->left);nums_node.push_back(node);dfs_inor(node->right);}TreeNode *increasingBST(TreeNode *root){if (root == nullptr){return nullptr;}nums_node.clear(); // 清空，防止多次調用污染dfs_inor(root);TreeNode *node = nums_node[0];for (int i = 0; i < nums_node.size() - 1; i++){nums_node[i]->left = nullptr;nums_node[i]->right = nums_node[i + 1];}nums_node.back()->left = nullptr;nums_node.back()->right = nullptr;/*** 這里需要注意的是細節* 最后的節點需要設置為null*/return node;}TreeNode *resNode;void inorder1(TreeNode *node){if (node == nullptr){return;}inorder(node->left);// 在中序遍歷的過程中修改節點指向resNode->right = node;node->left = nullptr;resNode = node;// 深得遞歸的精髓inorder(node->right);}TreeNode *increasingBSTs(TreeNode *root){TreeNode *dummyNode = new TreeNode(-1);resNode = dummyNode;inorder(root);return dummyNode->right;}/*** 給定二叉搜索樹的根結點 root* 返回值位于范圍 [low, high] 之間的所有結點的值的和。*/int rangeSumBST(TreeNode *root, int low, int high){/*** 二叉搜索樹是很是特殊的* 具有方便查找的特性*  */if (root == nullptr){return 0;}nums_node.clear();inorder(root);// 經歷一次中序遍歷int sum = 0;for (auto i : nums_node){if ((i->val >= low) && (i->val <= high)){sum += i->val;}}return sum;/*** 現在看來的話* 中序遍歷的邏輯是真的很香啊*/}/*** 如果二叉樹每個節點都具有相同的值，那么該二叉樹就是單值二叉樹。只有給定的樹是單值二叉樹時，才返回 true；否則返回 false。*/bool isUnivalTree(TreeNode *root){/* 單值二叉樹很好操作*/if (!root)return true;if (root->left && root->left->val != root->val)return false;if (root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);}/*** 在二叉樹中，根節點位于深度 0 處，每個深度為 k 的節點的子節點位于深度 k+1 處。如果二叉樹的兩個節點深度相同，但 父節點不同 ，則它們是一對堂兄弟節點。我們給出了具有唯一值的二叉樹的根節點 root ，以及樹中兩個不同節點的值 x 和 y 。只有與值 x 和 y 對應的節點是堂兄弟節點時，才返回 true 。否則，返回 false。*/// 返回當簽樹的深度TreeNode *x_parent = nullptr;TreeNode *y_parent = nullptr;int x_depth = -1;int y_depth = -1;void dfs(TreeNode *node, TreeNode *parent, int depth, int x, int y){if (!node)return;if (node->val == x){x_parent = parent;x_depth = depth;}if (node->val == y){y_parent = parent;y_depth = depth;}dfs(node->left, node, depth + 1, x, y);dfs(node->right, node, depth + 1, x, y);}bool isCousins(TreeNode *root, int x, int y){x_parent = y_parent = nullptr;x_depth = y_depth = -1;dfs(root, nullptr, 0, x, y);return x_depth == y_depth && x_parent != y_parent;}/*** 給出一棵二叉樹，其上每個結點的值都是 0 或 1 。每一條從根到葉的路徑都代表一個從最高有效位開始的二進制數。例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1，那么它表示二進制數 01101，也就是 13 。對樹上的每一片葉子，我們都要找出從根到該葉子的路徑所表示的數字。返回這些數字之和。題目數據保證答案是一個 32 位 整數。*/int sumRootToLeaf(TreeNode *root){if (root == nullptr){return 0;}vector<vector<int>> paths;vector<int> currentPath;dfs(root, currentPath, paths);// 將二進制數據轉為十進制并求和int sum = 0;for (const auto &path : paths){int num = 0;for (int val : path){num = num * 2 + val;num %= 1000000007; // 防止溢出的大數取模}sum += num;sum %= 1000000007; // 防止溢出的大數取模}return sum;}private:void dfs(TreeNode *node, vector<int> &currentPath, vector<vector<int>> &paths){if (node == nullptr){return;}currentPath.push_back(node->val);// 如果是葉子節點if (node->left == nullptr && node->right == nullptr){paths.push_back(currentPath);}// 遞歸處理左右子樹dfs(node->left, currentPath, paths);dfs(node->right, currentPath, paths);// 回溯currentPath.pop_back();/*** # 二叉樹DFS回溯過程演示## 🌳 二叉樹結構```plaintext1/ \2   3/ \4   5```## 📜 路徑記錄規則- **進入節點**：`currentPath.push_back(node->val)`- **離開節點**：`currentPath.pop_back()`（回溯）---## 🔍 分步演示（DFS順序：1 → 2 → 4 → 5 → 3）### 步驟 1：訪問節點 1```cppcurrentPath.push_back(1);```- `currentPath = [1]`- **狀態**：```plaintext當前路徑：1```### 步驟 2：訪問節點 2```cppcurrentPath.push_back(2);```- `currentPath = [1, 2]`- **狀態**：```plaintext當前路徑：1 → 2```### 步驟 3：訪問節點 4（葉子節點）```cppcurrentPath.push_back(4);paths.push_back(currentPath); // 保存路徑 [1,2,4]currentPath.pop_back();       // 回溯```- **操作后**：```plaintext已存路徑：[1,2,4]當前路徑：1 → 2```### 步驟 4：訪問節點 5（葉子節點）```cppcurrentPath.push_back(5);paths.push_back(currentPath); // 保存路徑 [1,2,5]currentPath.pop_back();       // 回溯```- **操作后**：```plaintext已存路徑：[1,2,4], [1,2,5]當前路徑：1 → 2```### 步驟 5：回溯到節點 1```cppcurrentPath.pop_back(); // 移除 2```- `currentPath = [1]`- **狀態**：```plaintext當前路徑：1```### 步驟 6：訪問節點 3（葉子節點）```cppcurrentPath.push_back(3);paths.push_back(currentPath); // 保存路徑 [1,3]currentPath.pop_back();       // 回溯```- **最終結果**：```plaintext所有路徑：[1,2,4],[1,2,5],[1,3]```---## ? 如果沒有回溯會怎樣？假設刪除 `pop_back()`：- 路徑會錯誤累積成 `[1,2,4,5,3]`- **錯誤原因**：子節點值未被移除，污染父節點路徑---## 📌 關鍵總結| 操作                | 作用                           | 類比               ||---------------------|-------------------------------|--------------------|| `push_back`         | 進入節點時記錄路徑             | 像用粉筆標記路口   || `pop_back`（回溯）  | 離開節點時清除標記             | 像擦掉粉筆標記     |**回溯保證了每條路徑的獨立性**，是DFS遍歷樹或圖的核心技巧。*/}/**又是一個一千行 *//*** 給你兩棵二叉樹，原始樹 original 和克隆樹 cloned，以及一個位于原始樹 original 中的目標節點 target。其中，克隆樹 cloned 是原始樹 original 的一個 副本 。請找出在樹 cloned 中，與 target 相同 的節點，并返回對該節點的引用（在 C/C++ 等有指針的語言中返回 節點指針，其他語言返回節點本身）。注意：你 不能 對兩棵二叉樹，以及 target 節點進行更改。只能 返回對克隆樹 cloned 中已有的節點的引用。*/TreeNode *getTargetCopy(TreeNode *original, TreeNode *cloned, TreeNode *target){/**這個問題就很是抽象啊 */if (cloned == nullptr){return nullptr;}if (cloned->val == target->val){return cloned; // 找到目標節點，返回克隆樹中的對應節點}// 遞歸查找左子樹TreeNode *leftResult = getTargetCopy(original, cloned->left, target);if (leftResult != nullptr){return leftResult;}/*** 優先查找左子樹：首先在 cloned 的左子樹中遞歸查找目標節點。如果找到了，直接返回，無需繼續查找右子樹。
再查找右子樹：如果左子樹中沒有找到目標節點，則繼續在 cloned 的右子樹中遞歸查找。如果右子樹中找到了目標節點，返回該節點；否則返回 nullptr。*/// 遞歸查找右子樹return getTargetCopy(original, cloned->right, target);}/*** 繼續  怎么能輕易的放棄* 給你一個 二叉樹 的根結點 root，該二叉樹由恰好 3 個結點組成：根結點、左子結點和右子結點。如果根結點值等于兩個子結點值之和，返回 true ，否則返回 false 。*/bool checkTree(TreeNode* root) {//  剛好恰有三個節點組成// if(root==nullptr)// {//     return false;// }// return root->val ==  (root->left->val + root->right->val);return root == nullptr ? false : root->val == (root->left->val + root->right->val);/*** 這是寫過的最簡單的題目了*/}int findSecondMinimumValue(TreeNode* root) {int ans = -1;int rootvalue = root->val;/*** lamada表達式是個神奇的運用 * 但是我還沒有熟悉和掌握* 完全沒有運用過  確實屬于一個小的弱項*/function<void(TreeNode*)> dfs = [&](TreeNode* node) {if (!node) {return;}if (ans != -1 && node->val >= ans) {return;}if (node->val > rootvalue) {ans = node->val;}dfs(node->left);dfs(node->right);};dfs(root);return ans;}
};struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
};TreeNode *sortedArrayToBST(vector<int> &nums)
{/*** 使用棧替換遞歸*/if (nums.empty()){return nullptr;}stack<tuple<TreeNode *, int, int>> s; // 定義棧TreeNode *root = nullptr;s.push(make_tuple(root, 0, nums.size() - 1));while (!s.empty()){auto [node, left, right] = s.top(); // 獲取棧頂元素s.pop();if (left > right){continue; // 如果左邊界大于右邊界，跳過}int mid = left + (right - left) / 2; // 找到中間元素node = new TreeNode(nums[mid]);      // 創建新節點if (root == nullptr){root = node; // 設置根節點}// 將右子樹和左子樹入棧s.push(make_tuple(node->right, mid + 1, right));s.push(make_tuple(node->left, left, mid - 1));}return root; // 返回構建好的樹
}int main(void)
{return 0;
}