Leetcode 热题100 之 二叉树3
1.二叉树展开为链表
思路分析：迭代法。对于每个节点，我们将其左子树放到右子树的位置。将原来的右子树接到新的右子树（也就是原来的左子树）的末端。移动到右子节点，继续处理下一节点，直到所有节点都处理完。
-
遍历当前节点，如果该节点有左子节点；
- 将左子树的最右节点找到（以便连接原来的右子树）；
- 将当前节点的右子树街道左子树的最右节点；
- 将当前节点的左子树放到右子树的位置，并将左子树置为空；
-
移动到右子节点，重复上述过程知道所有接二点都处理完毕。
具体实现代码(详解版）：
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* current = root;
while (current) {
if (current->left) {
// 找到左子树的最右节点
TreeNode* rightmost = current->left;
while (rightmost->right) {
rightmost = rightmost->right;
}
// 将当前节点的右子树接到左子树的最右节点
rightmost->right = current->right;
// 将左子树移动到右子树的位置，并将左子树置为空
current->right = current->left;
current->left = nullptr;
}
// 移动到右子节点，继续展开
current = current->right;
}
}
};
- 时间复杂度：O(n)，其中n是二叉树的节点数
- 空间复杂度：O(1),因为该方法是原地修改树，不需要额外的空间。
2.从前序与中序构造二叉树
思路分析：递归
- 先序遍历的第一个元素是树的根节点；
- 中序遍历中，根节点左侧的所有元素构成左子树，右侧的所有元素构成右子树；
- 所以我们可以先从先序遍历中提取根节点，然后在中序遍历中找到该节点的位置，将数组分为左子树和右子树的部分。重复递归，分别构造左右子树。
- inorder[0:index] 表示左子树的节点。
- inorder[index+1:] 表示右子树的节点。
具体实现代码（详解版）：
class Solution {
public:
// 哈希表，用于快速定位中序遍历中根节点的位置
unordered_map<int, int> inorderMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 将中序遍历的值与索引存入哈希表，便于快速查找根节点位置
for (int i = 0; i < inorder.size(); ++i) {
inorderMap[inorder[i]] = i;
}
// 开始递归构建二叉树
return buildSubTree(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
private:
// 递归构建子树
TreeNode* buildSubTree(const vector<int>& preorder, int preStart, int preEnd,
int inStart, int inEnd) {
// 如果索引越界，返回空节点
if (preStart > preEnd || inStart > inEnd) return nullptr;
// 先序遍历的第一个节点是根节点
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int inRootIndex = inorderMap[rootVal];
int leftTreeSize = inRootIndex - inStart;
// 构建左子树
root->left = buildSubTree(preorder, preStart + 1, preStart + leftTreeSize,
inStart, inRootIndex - 1);
// 构建右子树
root->right = buildSubTree(preorder, preStart + leftTreeSize + 1, preEnd,
inRootIndex + 1, inEnd);
return root;
}
};
- 时间复杂度：O(n),其中n是节点数；
- 空间复杂度：O(n),递归栈的最大深度为树的高度，平均情况下为O（log n),最坏情况下为O(n)。
3.路径总和III
思路分析：DFS
- 路径的定义：路径可以从任意节点开始，并且只能向下（即只能从父节点到子节点）。这意味着我们需要考虑每个节点作为路径的起点。
- 递归遍历：我们需要递归遍历每个节点，记录当前路径的和，并检查是否有满足条件的路径
- 使用哈希表：为了高效地查找满足条件的路径，我们可以使用哈希表来存储当前路径和的出现次数。当我们在某个节点上访问时，计算到该节点的路径和。如果该路径和减去 targetSum 的值已经存在于哈希表中，那么就表示存在这样的路径。
- 处理路径和的增加与减少：在进入某个节点时增加路径和的计数，离开节点时减少路径和的计数，这样可以确保只统计以该节点为起点的路径。
- dfs函数
- 当节点为空时返回 0。
- 更新当前路径和 currentSum。
- 通过 currentSum - targetSum 在哈希表中查找满足条件的路径数，并累加到 count
- 更新哈希表，记录当前路径和出现的次数。
- 递归访问左子树和右子树，累加找到的路径数。
- 回溯时，减少当前路径和的计数以防止影响其他路径的统计。
具体实现代码（详解版）：
class Solution {
public:
// 主函数，初始化参数并开始递归
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> prefixSumCount; // 使用 long long 防止溢出
prefixSumCount[0] = 1; // 处理从根节点到当前节点的路径和为 targetSum 的情况
return dfs(root, targetSum, 0, prefixSumCount);
}
private:
// 深度优先搜索函数
int dfs(TreeNode* node, long long targetSum, long long currentSum, unordered_map<long long, int>& prefixSumCount) {
if (!node) return 0; // 如果节点为空，返回 0
// 更新当前路径和
currentSum += node->val;
int count = prefixSumCount[currentSum - targetSum]; // 找到满足条件的路径数
// 更新前缀和的出现次数
prefixSumCount[currentSum]++;
// 递归遍历左右子树
count += dfs(node->left, targetSum, currentSum, prefixSumCount);
count += dfs(node->right, targetSum, currentSum, prefixSumCount);
// 在回溯时，减少当前路径和的计数
prefixSumCount[currentSum]--;
return count; // 返回找到的路径数
}
};
- 时间复杂度：O(n),其中n是节点数；
- 空间复杂度：O(n),主要用于哈希表的存储和递归栈的深度
4.二叉树的最近公共祖先
要找到二叉树中两个节点的最近公共祖先（Lowest Common Ancestor, LCA），可以使用递归的深度优先搜索（DFS）方法。下面是实现的思路和代码。
思路分析：
-
递归遍历：使用DFS递归遍历树的每个节点，直到找到目标节点p或q；
-
返回值的含义：
- 如果当前节点为null，返回null；
- 如果当前节点是p或q，返回该节点；
- 如果左子树或者右子树找到了一个目标节点，则说明当前节点可能是LCA；
-
判断LCA
- 如果左右子树分别返回p和q，则当前节点就是LCA；
- 如果仅有一个子树返回目标节点，说明目标节点在该子树中，继续返回；
- 即为如果左子树和右子树都返回非空节点，当前节点就是最近公共祖先。；
- 否则，返回非空的子树节点（如果存在的话）。
具体实现代码（详解版）：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果根节点为空或找到 p 或 q，直接返回根节点
if (root == nullptr || root == p || root == q) {
return root;
}
// 递归查找左子树和右子树
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 如果左子树和右子树都有找到的节点，当前节点就是 LCA
if (left && right) {
return root;
}
// 否则返回找到的子树节点
return left ? left : right;
}
};
- 时间复杂度：O(n),n为节点总数；
- 空间复杂度：O(n),用于存储前缀和
5.二叉树的最大路径和
思路分析：要找到二叉树中的最大路径和，可以使用深度优先搜索（DFS）的方法。这里的关键在于如何计算以每个节点为根的最大路径和，并在递归过程中更新全局最大路径和。
- 定义：路径和是指路径中所有节点的值之和，我们需要计算每个节点的左右子树的路径和，并通过该节点形成的路径进行更新。
- 递归函数：
- 在每个节点上，选择将其值与其左子树和右子树的最大路径和相加，得到经过当前节点的路径和；
- 需要保持一个全局变量来记录当前找到的最大路径和；
- 处理路径和：
- 对于每个节点，我们考虑两种情况：
- 以当前节点为根的路径和（可能由左右子树的路径和相加得到）；
- 单独的左子树和右子树的路径和（仅向上返回给父节点的值）
- 对于每个节点，我们考虑两种情况：
具体实现代码(详解版）：
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN; // 初始化最大路径和
maxGain(root, maxSum); // 调用递归函数
return maxSum; // 返回结果
}
private:
// 计算以当前节点为根的最大路径和
int maxGain(TreeNode* node, int& maxSum) {
if (!node) return 0; // 节点为空，返回 0
// 递归计算左右子树的最大路径和，负值不贡献，取 0
int leftGain = max(maxGain(node->left, maxSum), 0);
int rightGain = max(maxGain(node->right, maxSum), 0);
// 计算经过当前节点的路径和
int currentPathSum = node->val + leftGain + rightGain;
// 更新全局最大路径和
maxSum = max(maxSum, currentPathSum);
// 返回当前节点的最大贡献（给父节点）
return node->val + max(leftGain, rightGain);
}
};
- 时间复杂度：O(n)，每个节点只被访问一次；
- 空间复杂度：O(h),h为树的高度。