LeetCode:12day:二叉树（3）
🌲 二叉树算法经典题目总结（3）（C++ 实现）
二叉树是数据结构中的重要组成部分，也是面试中的高频考点。本文总结了四道经典的二叉树问题，涵盖不同类型的算法技巧，帮助你更好地理解和掌握二叉树的操作。
🟢 1. 从前序与中序遍历序列构造二叉树（Construct Binary Tree from Preorder and Inorder Traversal）
📄 题目描述：
给定一棵树的前序遍历 preorder 和中序遍历 inorder 的结果，重建这棵树。
🧠 解题思路（简洁版）
- 迭代构建：
⏱️ 复杂度分析
- 时间复杂度：
O(n)，其中n为树的节点数。 - 空间复杂度：
O(n)，栈空间。
✅ C++ 实现
class Solution {public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty()) { return nullptr; } TreeNode* root = new TreeNode(preorder[0]); stack<TreeNode*> stk; stk.push(root); int inorderIndex = 0; for (int i = 1; i < preorder.size(); ++i) { int preorderVal = preorder[i]; TreeNode* node = stk.top(); if (node->val != inorder[inorderIndex]) { node->left = new TreeNode(preorderVal); stk.push(node->left); } else { while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) { node = stk.top(); stk.pop(); ++inorderIndex; } node->right = new TreeNode(preorderVal); stk.push(node->right); } } return root; }};🟢 2. 路径总和 III（Path Sum III）
📄 题目描述：
给定一个二叉树的根节点 root 和一个整数 targetSum，返回路径总和等于给定目标和的路径数目。
🧠 解题思路（简洁版）
- 前缀和 + DFS：
- 使用哈希表记录前缀和出现的次数。
- 递归遍历树，计算当前路径的前缀和。
- 检查是否存在满足条件的子路径（即
curr - targetSum是否在哈希表中）。 - 更新哈希表，回溯时撤销更新。
⏱️ 复杂度分析
- 时间复杂度：
O(n)，其中n为树的节点数。 - 空间复杂度：
O(n)，哈希表和递归栈空间。
✅ C++ 实现
class Solution {public: unordered_map<long long, int> prefix; int dfs(TreeNode* root, long long curr, int targetSum) { if (!root) return 0; int ret = 0; curr += root->val; if (prefix.count(curr - targetSum)) { ret = prefix[curr - targetSum]; } prefix[curr]++; ret += dfs(root->left, curr, targetSum); ret += dfs(root->right, curr, targetSum); prefix[curr]--; return ret; } int pathSum(TreeNode* root, int targetSum) { prefix[0] = 1; return dfs(root, 0, targetSum); }};🟢 3. 二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）
📄 题目描述：
给定一个二叉树的根节点 root 和两个节点 p 和 q，找到它们的最近公共祖先。
🧠 解题思路（简洁版）
- 递归寻找公共祖先：
- 递归遍历树，返回当前子树是否包含目标节点
p或q。 - 若当前节点的左右子树分别包含
p和q，或当前节点是p或q且子树包含另一个目标节点，则当前节点是最近公共祖先。 - 更新答案并返回。
- 递归遍历树，返回当前子树是否包含目标节点
⏱️ 复杂度分析
- 时间复杂度：
O(n)，其中n为树的节点数。 - 空间复杂度：
O(h)，其中h为树的高度（递归栈空间）。
✅ C++ 实现
class Solution {public: TreeNode* ans; bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) return false; bool lson = dfs(root->left, p, q); bool rson = dfs(root->right, p, q); if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) { ans = root; } return lson || rson || (root->val == p->val || root->val == q->val); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { dfs(root, p, q); return ans; }};🟢 4. 二叉树中的最大路径和（Binary Tree Maximum Path Sum）
📄 题目描述：
给定一个二叉树的根节点 root，返回树中的最大路径和。路径可以不经过根节点，但必须是连续的。
🧠 解题思路（简洁版）
- 递归计算最大路径和：
- 对于每个节点，计算经过该节点的最大路径和（左子树最大增益 + 右子树最大增益 + 当前节点值）。
- 更新全局最大路径和。
- 返回当前节点的最大增益（当前节点值 + 左右子树中较大的增益）。
⏱️ 复杂度分析
- 时间复杂度：
O(n)，其中n为树的节点数。 - 空间复杂度：
O(h)，其中h为树的高度（递归栈空间）。
✅ C++ 实现
class Solution {private: int maxSum = INT_MIN;public: int maxGain(TreeNode* node) { if (node == nullptr) return 0; int leftGain = max(maxGain(node->left), 0); int rightGain = max(maxGain(node->right), 0); int priceNewpath = node->val + leftGain + rightGain; maxSum = max(maxSum, priceNewpath); return node->val + max(leftGain, rightGain); } int maxPathSum(TreeNode* root) { maxGain(root); return maxSum; }};📌 总结
希望本文对你有所帮助！如果你还有其他问题，欢迎继续提问。
