目录
二叉树
1. 94. 二叉树的中序遍历
2. 98. 验证二叉搜索树
3. 101. 对称二叉树
4.102. 二叉树的层序遍历
5. 104. 二叉树的最大深度
6. 105. 从前序与中序遍历序列构造二叉树
7. 114. 二叉树展开为链表
8. 226. 翻转二叉树
9. 236. 二叉树的最近公共祖先
二叉树
1. 94. 二叉树的中序遍历
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
// 二叉树的遍历
class Solution {
public:
vector<int> result; // 用来存储中序遍历的结果的向量
// 中序遍历的递归函数
void inorder(TreeNode* root){
if(!root) return; // 如果节点为空,直接返回
inorder(root->left); // 递归遍历左子树
result.push_back(root->val); // 将当前节点的值加入结果向量
inorder(root->right); // 递归遍历右子树
}
// 主函数,返回中序遍历的结果
vector<int> inorderTraversal(TreeNode* root) {
inorder(root); // 调用中序遍历的递归函数
return result; // 返回结果向量
}
};
解释:
- 从根节点开始,先访问左子树,然后访问根节点,最后访问右子树。
- 对于当前的二叉树:
- 根节点为
1
,先访问左子树,但是左子树为空,因此直接访问根节点1
,将1
加入结果数组。 - 然后访问右子树,右子树是节点
2
。 - 对于节点
2
,先访问左子树,即节点3
。访问节点3
,将3
加入结果数组。 - 然后访问根节点
2
,将2
加入结果数组。
- 根节点为
2. 98. 验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 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:
vector<int> v; // 存储遍历结果的向量// 递归遍历二叉树,进行中序遍历
bool recursive(TreeNode* root){
if(!root) return true; // 如果当前节点为空,返回true// 递归遍历左子树
recursive(root->left);
// 将当前节点的值加入到结果向量中
v.push_back(root->val);
// 递归遍历右子树
recursive(root->right);return true; // 返回true表示遍历成功
}// 判断二叉树是否为有效的二叉搜索树
bool isValidBST(TreeNode* root) {
recursive(root); // 执行中序遍历,将结果存入向量v// 检查向量v中的值是否是严格递增的
for(int i{}; i < v.size(); ++i){
if(i && v[i-1] >= v[i]){ // 如果当前值不大于前一个值
return false; // 不是有效的二叉搜索树
}
}
return true; // 所有值都满足条件,返回true
}
};
3. 101. 对称二叉树
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3] 输出:false
提示:
- 树中节点数目在范围
[1, 1000]
内 -100 <= Node.val <= 100
/**
* 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:
// 递归函数,检查两个子树是否是镜像对称的
bool recursive(TreeNode* left, TreeNode* right) {
// 如果两个子树都为空,则它们对称,返回true
if (!left && !right) return true;
// 如果一个子树为空,而另一个子树不为空,则不对称,返回false
else if (left && !right) return false;
else if (!left && right) return false;// 如果两个子树的根节点值不相等,则不对称,返回false
if (left->val != right->val) return false;
// 递归检查左子树的左子节点与右子树的右子节点是否对称,以及
// 左子树的右子节点与右子树的左子节点是否对称
bool flag = recursive(left->left, right->right);
bool flag1 = recursive(left->right, right->left);// 只有当左右两侧子树都对称时,返回true;否则返回false
return flag && flag1;
}// 检查整个树是否是对称的
bool isSymmetric(TreeNode* root) {
// 如果根节点为空,树是对称的,返回true
if (!root) return true;// 调用递归函数,检查根节点的左子树和右子树是否是镜像对称的
return recursive(root->left, root->right);
}
};
4.102. 二叉树的层序遍历
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
// 二叉树的遍历
/**
* 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:
vector<vector<int>> result; // 存储每一层节点值的结果
// 层次遍历二叉树
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {}; // 如果根节点为空,返回空的二维向量
queue<TreeNode*> q; // 创建一个队列用于存储待遍历的节点
q.push(root); // 将根节点入队
// 当队列不为空时,继续遍历
while (!q.empty()) {
int n = q.size(); // 当前层的节点数量
vector<int> v1; // 用于存储当前层的节点值
// 遍历当前层的所有节点
for (int i{}; i < n; ++i) {
TreeNode* node = q.front(); // 获取队列的前端节点
q.pop(); // 将该节点出队
v1.emplace_back(node->val); // 将该节点的值添加到当前层结果中
// 将左右子节点入队(如果存在)
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(v1); // 将当前层的节点值存入结果中
}
return result; // 返回结果
}
};
5. 104. 二叉树的最大深度
给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:3
示例 2:
输入:root = [1,null,2] 输出:2
提示:
- 树中节点的数量在
[0, 104]
区间内。 -100 <= Node.val <= 100
/**
* 定义二叉树节点的结构。
* 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:
// 计算二叉树的最大深度的函数
int maxDepth(TreeNode* root) {
// 如果当前节点为空(基例),返回 0
if (!root) return 0; // 更正了原代码中的 {} 为 0
// 递归计算左子树和右子树的深度
// 返回两个深度的最大值加上当前节点的深度(1)
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
6. 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]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
和inorder
均 无重复 元素inorder
均出现在preorder
preorder
保证 为二叉树的前序遍历序列inorder
保证 为二叉树的中序遍历序列
// 树的遍历
/**
* 定义二叉树节点的结构。
* 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:
// 辅助函数:递归构造二叉树
TreeNode* recursive(vector<int>& inorder, vector<int>& preorder) {
// 递归的终止条件:如果前序遍历的数组为空,返回空节点
if (preorder.size() == 0) return nullptr;// 前序遍历的第一个元素是根节点
TreeNode* root = new TreeNode(preorder[0]);// 在中序遍历中找到根节点的位置,根节点左边的是左子树,右边的是右子树
int index = 0;
for (int i = 0; i < inorder.size(); ++i) {
if (inorder[i] == preorder[0]) {
index = i; // 找到根节点在中序遍历中的位置
break;
}
}// 根据中序遍历分割出左子树和右子树的节点范围
vector<int> leftInorder(inorder.begin(), inorder.begin() + index); // 左子树的中序遍历
vector<int> rightInorder(inorder.begin() + index + 1, inorder.end()); // 右子树的中序遍历// 根据前序遍历分割出左子树和右子树的节点范围
vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size()); // 左子树的前序遍历
vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end()); // 右子树的前序遍历// 递归构建左子树和右子树
root->left = recursive(leftInorder, leftPreorder); // 构建左子树
root->right = recursive(rightInorder, rightPreorder); // 构建右子树return root; // 返回当前的根节点
}// 主函数:根据前序遍历和中序遍历构造二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 如果前序遍历或中序遍历为空,直接返回空树
if (preorder.size() == 0 || inorder.size() == 0) return nullptr;// 调用辅助函数进行递归构造
return recursive(inorder, preorder);
}
};
解释:
vector<int> leftInorder(inorder.begin(), inorder.begin() + index)
的范围在数学上可以表示为 [0,index)[0, \text{index})[0,index)。
class Solution {
private:
unordered_map<int, int> inorderMap; // 存储中序遍历的值到索引的映射
int preorderIndex = 0; // 前序遍历的当前索引// 递归帮助函数,用于构建树
TreeNode* buildTreeHelper(vector<int>& preorder, int left, int right) {
if (right < left) return nullptr; // 基本情况:没有节点可构建,返回 nullptr// 获取当前根节点的值并创建 TreeNode
int rootVal = preorder[preorderIndex++];
TreeNode* root = new TreeNode(rootVal);
// 获取当前根值在中序数组中的索引
int inorderIndex = inorderMap[rootVal];// 递归构建左子树和右子树
root->left = buildTreeHelper(preorder, left, inorderIndex - 1); // 左子树范围
root->right = buildTreeHelper(preorder, inorderIndex + 1, right); // 右子树范围
return root; // 返回构建的子树
}public:
// 主函数,从前序和中序遍历构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preorderIndex = 0; // 重置前序遍历索引
// 填充中序数组的值到索引的映射
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i; // 记录每个值在中序数组中的索引
}
// 开始递归构建树
return buildTreeHelper(preorder, 0, inorder.size() - 1);
}
};
解释:
unordered_map
用于存储中序遍历中的值与其对应的索引,以便快速查找。preorderIndex
用于追踪前序遍历中当前的索引,以获取根节点的值。buildTreeHelper
是一个递归函数,用于构建树。通过指定的范围(left
和right
)构建子树,并返回构建的节点。- 基本情况:如果当前的范围没有元素(
right < left
),则返回nullptr
。 - 树的构建过程:
- 创建根节点。
- 查找根节点在中序数组中的位置。
- 递归构建左子树和右子树。
7. 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]
提示:
- 树中结点数在范围
[0, 2000]
内 -100 <= Node.val <= 100
class Solution {
public:
// 主函数,负责将二叉树展平
void flatten(TreeNode* root) {
vector<TreeNode*> l; // 创建一个向量用于存储树节点
preorderTraversal(root, l); // 进行前序遍历并将节点存入向量
int n = l.size(); // 获取节点数量
// 遍历节点列表,从第二个节点开始
for (int i = 1; i < n; i++) {
TreeNode *prev = l.at(i - 1); // 上一个节点
TreeNode *curr = l.at(i); // 当前节点
prev->left = nullptr; // 将上一个节点的左指针设为 nullptr
prev->right = curr; // 将上一个节点的右指针指向当前节点
}
}
// 辅助函数,进行前序遍历
void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {
if (root != NULL) { // 如果当前节点不为空
l.push_back(root); // 将当前节点添加到向量中
preorderTraversal(root->left, l); // 递归遍历左子树
preorderTraversal(root->right, l); // 递归遍历右子树
}
}
};
解释:
-
flatten 函数:
- 功能: 将给定的二叉树
root
展平。 - 步骤:
- 创建一个
vector<TreeNode*> l
来存储树的节点。 - 调用
preorderTraversal
函数,传入根节点和节点列表,进行前序遍历。 - 根据前序遍历的顺序,遍历存储节点的列表
l
,将每个节点的左指针设为nullptr
,右指针指向下一个节点,最终实现链表化。
- 创建一个
- 功能: 将给定的二叉树
-
preorderTraversal 函数:
- 功能: 递归进行二叉树的前序遍历,将访问到的节点存入列表
l
。 - 步骤:
- 检查当前节点
root
是否为空,如果不为空,则将其添加到列表中。 - 递归调用左子树和右子树进行遍历。
- 检查当前节点
- 功能: 递归进行二叉树的前序遍历,将访问到的节点存入列表
8. 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 = [] 输出:[]
提示:
- 树中节点数目范围在
[0, 100]
内 -100 <= Node.val <= 100
// 递归
class Solution {/**
* Definition for a binary tree node.
* struct TreeNode {
* int val; // 节点的值
* TreeNode *left; // 指向左子节点的指针
* TreeNode *right; // 指向右子节点的指针
* TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数,初始化值为0,左右子节点为nullptr
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值的构造函数,初始化节点值
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 带值和左右子节点的构造函数
* };
*/
public:
// 辅助函数:递归翻转二叉树
TreeNode* invert(TreeNode* root) {
// 如果当前节点为空,直接返回空指针
if (!root) return root;
// 保存当前节点的左子树和右子树
TreeNode* left = root->left; // 记录左子树
TreeNode* right = root->right; // 记录右子树
// 交换左右子树
root->right = left; // 将左子树放到右子树的位置
root->left = right; // 将右子树放到左子树的位置
// 递归翻转右子树
if (root->right) invert(root->right); // 如果右子树存在,递归翻转
// 递归翻转左子树
if (root->left) invert(root->left); // 如果左子树存在,递归翻转
// 返回当前节点,完成翻转
return root;
}
// 主函数:调用辅助函数进行翻转
TreeNode* invertTree(TreeNode* root) {
return invert(root); // 返回翻转后的树的根节点
}
};
解释:
return root;
: 当返回的是当前节点或树的根节点(指针)。常用于递归结构中返回操作后的节点。return nullptr;
: 当明确表示返回一个空指针时,使用nullptr
,这种写法更加语义化。return;
: 当函数不需要返回任何值时,直接用return;
来结束函数。它只能用于void
类型的函数。
9. 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
均存在于给定的二叉树中。
// 递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val; // 节点的值
* TreeNode *left; // 左子节点指针
* TreeNode *right; // 右子节点指针
* // 构造函数,初始化节点值,左右子节点为 NULL
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/class Solution {
public:
// 辅助递归函数,用于查找 p 和 q 的最近公共祖先
TreeNode* recursive(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果当前节点是 p、q 中的一个,或者当前节点为空,直接返回当前节点
if (root == p || root == q || !root) return root;// 递归查找左子树中的 p 和 q
TreeNode* left = recursive(root->left, p, q);
// 递归查找右子树中的 p 和 q
TreeNode* right = recursive(root->right, p, q);// 如果 p 和 q 分别在当前节点的左右子树中,当前节点就是最近公共祖先
if (left && right) return root;
// 如果只有左子树中有 p 或 q,返回左子树的结果
else if (left && !right) return left;
// 如果只有右子树中有 p 或 q,返回右子树的结果
else if (!left && right) return right;
// 如果左右子树都没有 p 和 q,返回空指针
else return {};
}// 主函数,调用递归函数来查找最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return recursive(root, p, q); // 返回递归查找的结果
}
};