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);// 如果左子树和右子树都有找到的节点，当前节点就是 LCAif (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// 递归计算左右子树的最大路径和，负值不贡献，取 0int 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);}
};