二叉树的建立与遍历
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 函数：根据层次遍历结果构建二叉树
TreeNode* buildTree(const vector<int*>& nodes) {
if (nodes.empty() || nodes[0] == nullptr) return nullptr;
// 创建根节点
TreeNode* root = new TreeNode(*nodes[0]);
queue<TreeNode*> q;
q.push(root);
int i = 1; // 用于遍历输入数组
while (!q.empty() && i < nodes.size()) {
TreeNode* current = q.front();
q.pop();
// 创建左子节点
if (i < nodes.size() && nodes[i] != nullptr) {
current->left = new TreeNode(*nodes[i]);
q.push(current->left);
}
i++;
// 创建右子节点
if (i < nodes.size() && nodes[i] != nullptr) {
current->right = new TreeNode(*nodes[i]);
q.push(current->right);
}
i++;
}
return root;
}
// 辅助函数：打印二叉树（层次遍历）
void printTree(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node) {
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
} else {
cout << "null ";
}
}
cout << endl;
}
int main() {
// 输入层次遍历结果
vector<int> input = {1, 2, 3, -1, 5, -1, 4}; // 使用 -1 表示 null
vector<int*> nodes;
for (int val : input) {
nodes.push_back(val == -1 ? nullptr : new int(val));
}
// 构建二叉树
TreeNode* root = buildTree(nodes);
// 打印构建的二叉树
cout << "构建的二叉树层次遍历结果为：" << endl;
printTree(root);
return 0;
}
hot100_94.二叉树的中序遍历
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
hot100_102.二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res = {};
if(root == nullptr) return res;
queue<TreeNode*> Q;
Q.push(root);
while(!Q.empty()){
int k = Q.size();
res.push_back(vector<int>{});
for(int i = 0; i < k ; i++){
TreeNode *temp = Q.front();
res.back().push_back(temp->val);
if(temp->left!=nullptr) Q.push(temp->left);
if(temp->right!=nullptr) Q.push(temp->right);
Q.pop();
}
}
return res;
}
};
hot100_199.二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
**输入：**root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
**输入：**root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
**输入：**root = [1,null,3]
输出：[1,3]
示例 4：
**输入：**root = []
输出：[]
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<vector<int>> res = levelOrder(root);
vector<int> result;
for(int i=0; i<res.size(); i++){
result.push_back(res[i].back());
}
return result;
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res = {};
if(root == nullptr) return res;
queue<TreeNode*> Q;
Q.push(root);
while(!Q.empty()){
int k = Q.size();
res.push_back(vector<int>{});
for(int i = 0; i < k ; i++){
TreeNode *temp = Q.front();
res.back().push_back(temp->val);
if(temp->left!=nullptr) Q.push(temp->left);
if(temp->right!=nullptr) Q.push(temp->right);
Q.pop();
}
}
return res;
}
};
hot100_114.二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终null
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
class Solution {
public:
void flatten(TreeNode* root) {
vector<TreeNode*> l;
preorderTraversal(root, l);
int n = l.size();
for (int i = 1; i < n; i++) {
l[i-1]->left = nullptr;
l[i-1]->right = l[i];
}
}
void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {
if (root != NULL) {
l.push_back(root);
preorderTraversal(root->left, l);
preorderTraversal(root->right, l);
}
}
};
hot100_105.从前序和中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
class Solution{
private:
unordered_map<int, int> indexMap;
int i;
public:
TreeNode* myBuildTree(vector<int>& pre, vector<int>& in, int l, int r){
if(l > r || i >= pre.size()) return nullptr;
TreeNode *root = new TreeNode;
root->val = pre[i];
int k = indexMap[pre[i]];//定位根节点在中序序列中的下标
i++;
root->left = myBuildTree(pre, in, l, k-1);//[l,k-1]为左子树的范围
root->right = myBuildTree(pre, in, k+1, r);//[k+1,r]为右子树的范围
return root;
}
TreeNode* buildTree(vector<int>& preOrder, vector<int>& inOrder){
for(int k = 0; k < inOrder.size(); k++){
indexMap[inOrder[k]] = k;
}
i = 0;
return myBuildTree(preOrder, inOrder, 0, preOrder.size());
}
};
hot100_104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
hot100_226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
hot100_101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root->left, root->right);
}
};
hot100_543.二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
class Solution {
int ans;
int depth(TreeNode* rt){
if (rt == NULL) {
return 0; // 访问到空节点了，返回0
}
int L = depth(rt->left); // 左儿子为根的子树的深度
int R = depth(rt->right); // 右儿子为根的子树的深度
ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
return max(L, R) + 1; // 返回该节点为根的子树的深度
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
};
hot100_108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size()-1);
}
TreeNode* helper(vector<int>& nums, int left, int right) {
// cout << left <<" " << right <<endl;
if(right < left) return nullptr;
int mid = (right + left)/2;
TreeNode *root = new TreeNode;
root->val = nums[mid];
root->left = helper(nums, left, mid - 1);
root->right = helper(nums, mid + 1, right);
return root;
}
};
hot100_98.验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
class Solution {
public:
bool helper(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) {
return true;
}
if (root -> val <= lower || root -> val >= upper) {
return false;
}
return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};
hot100_230.二叉搜索树中第K小元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode *> stack;
while (root != nullptr || stack.size() > 0) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
root = stack.top();
stack.pop();
--k;
if (k == 0) {
break;
}
root = root->right;
}
return root->val;
}
};
hot100_437.路径总和3
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
二叉树的节点个数的范围是[0,1000]-109 <= Node.val <= 109-1000 <= targetSum <= 1000class Solution { private: int count; unordered_map<long long, int> hashMap;//<前缀和,出现次数> int target; public: void dfs(TreeNode* root, long long sum){ if (root == nullptr) return; sum += root->val; //计算当前前缀和 if(hashMap.find(sum - target) != hashMap.end()){ //如果hash表中存在当前前缀和a减去目标和的前缀和b，及存在目标路径 //路径就是当前节点到前缀和为b之间 count += hashMap[sum - target]; } hashMap[sum] ++;//更新出现的前缀和以及次数 dfs(root->left, sum); dfs(root->right, sum); //当遍历了一个节点的左右子树后，需要把当前节点的前缀和次数-1 hashMap[sum]--; } int pathSum(TreeNode* root, int targetSum) { count = 0; target = targetSum; hashMap.clear(); hashMap[0] = 1; //插入前缀和为0出现的次数为1 dfs(root, 0); return count; } };hot100_560.和为K的子数组类似
给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1：
输入：nums = [1,1,1], k = 2 输出：2示例 2：
输入：nums = [1,2,3], k = 3 输出：2
class Solution{
public:
int subarraySum(vector<int>& nums, int k){
unordered_map<int, int> hashMap;
hashMap[0] = 1;
int count = 0; // 记录满足条件的子数组个数
int prefixSum = 0; // 初始化前缀和
for (int num : nums) {
prefixSum += num; // 计算当前的前缀和
// 检查是否存在 prefix_sum - k 的前缀和
if (hashMap.find(prefixSum - k) != hashMap.end()) {
count += hashMap[prefixSum - k]; // 加上满足条件的前缀和个数
}
hashMap[prefixSum]++; // 更新哈希表中的当前前缀和出现次数
}
return count;
}
};
hot100_236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围[2, 105]内。-109 <= Node.val <= 109所有Node.val互不相同。p != q`p` 和 `q` 均存在于给定的二叉树中。思路：
终止条件：
当越过叶节点，则直接返回 null ；
当 root 等于 p,q ，则直接返回 root ；递推：
递归左子节点，返回值记为 left ；
递归右子节点，返回值记为 right ；返回值： 根据 left 和 right ，可展开为四种情况；
（1）当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
（2）当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
（3）当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
3.1 p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ；
3.2 p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
（4）当 left 不为空 ， right 为空 ：与情况 3. 同理；
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left == nullptr && right == nullptr) return nullptr; // 1.
if(left == nullptr) return right; // 3.
if(right == nullptr) return left; // 4.
return root; // 2. if(left != null and right != null)
}
};
hot100_124.二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 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;
}
};