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);
else
return 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> ¤tPath, 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 5
dfs(1)
│
├─ dfs(2)
│ ├─ dfs(4) → 1
│ └─ dfs(5) → 1
│ l=1, r=1, max_diameter=2, return 2
│
└─ dfs(3) → 1
l=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);
else
return 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> ¤tPath, 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回溯过程演示
## 🌳 二叉树结构
```plaintext
1
/ \
2 3
/ \
4 5
```
## 📜 路径记录规则
- **进入节点**：`currentPath.push_back(node->val)`
- **离开节点**：`currentPath.pop_back()`（回溯）
---
## 🔍 分步演示（DFS顺序：1 → 2 → 4 → 5 → 3）
### 步骤 1：访问节点 1
```cpp
currentPath.push_back(1);
```
- `currentPath = [1]`
- **状态**：
```plaintext
当前路径：1
```
### 步骤 2：访问节点 2
```cpp
currentPath.push_back(2);
```
- `currentPath = [1, 2]`
- **状态**：
```plaintext
当前路径：1 → 2
```
### 步骤 3：访问节点 4（叶子节点）
```cpp
currentPath.push_back(4);
paths.push_back(currentPath); // 保存路径 [1,2,4]
currentPath.pop_back(); // 回溯
```
- **操作后**：
```plaintext
已存路径：[1,2,4]
当前路径：1 → 2
```
### 步骤 4：访问节点 5（叶子节点）
```cpp
currentPath.push_back(5);
paths.push_back(currentPath); // 保存路径 [1,2,5]
currentPath.pop_back(); // 回溯
```
- **操作后**：
```plaintext
已存路径：[1,2,4], [1,2,5]
当前路径：1 → 2
```
### 步骤 5：回溯到节点 1
```cpp
currentPath.pop_back(); // 移除 2
```
- `currentPath = [1]`
- **状态**：
```plaintext
当前路径：1
```
### 步骤 6：访问节点 3（叶子节点）
```cpp
currentPath.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;
}