1.二叉树的中序遍历
思路分析1（递归）：通过一个辅助函数 inorderHelper，递归地访问左子树、根节点和右子树，实现中序遍历。
具体实现代码（详解版）：
class Solution {
public:
void inorderHelper(TreeNode* root, vector<int>& result) {
if (root == nullptr) return; // 基本情况：空节点
inorderHelper(root->left, result); // 递归访问左子树
result.push_back(root->val); // 访问根节点
inorderHelper(root->right, result); // 递归访问右子树
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderHelper(root, result); // 调用辅助函数
return result;
}
};
思路分析2（迭代法，使用栈模拟）
- 初始化
- 创建一个栈stack用于存储节点
- 设置一个指针current指向根节点root
- 遍历左子树
- 进入循环，在current非空的情况下
- 将当前节点current入栈
- 移动current到当前节点的左子节点，继续尝试访问左子树
- 当到达最左端时，current会为nullptr，这时完成左子树的遍历
- 进入循环，在current非空的情况下
- 访问跟根节点
- 从栈中弹出一个节点，将其值添加到结果数组result中；
- 弹出的节点就是当前子树的根节点，按照中序遍历的顺序，我们在遍历完左子树后应该访问根节点。
- 遍历右子树
- 将 current 移动到右子节点，并开始新一轮的循环以遍历右子树（如果右子树存在，会重复步骤 2 和 3
- 如果右子树为空，则会弹出下一个节点并继续处理，直到栈为空且 current 为 nullptr 时结束遍历。
具体实现代码（详解版）：
/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stack;
TreeNode* current = root;
while(current != nullptr || !stack.empty()){
//将左字节点入栈直到最左端
while(current != nullptr){
stack.push(current);
current = current->left;
}
//处理栈顶节点（左根右中的根）
current = stack.top();
stack.pop();
result.push_back(current->val);//访问根节点
//转到右子树
current = current->right;
}
return result;
}
};
2.二叉数的最大深度
思路分析1（递归，DFS）：递归方法利用树的定义，每个节点的深度是其左子树和右子树深度的最大值加 1。根节点的深度就是整个树的深度。
具体实现代码（详解版）：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0; // 空节点深度为 0
int leftDepth = maxDepth(root->left); // 递归计算左子树深度
int rightDepth = maxDepth(root->right); // 递归计算右子树深度
return max(leftDepth, rightDepth) + 1; // 取左右子树的最大深度并加 1
}
};
思路分析2（迭代，BFS）：可以使用队列进行广度优先搜索（BFS）。每次遍历到下一层时，深度增加 1。最终的深度就是树的最大深度。
具体实现代码（详解版）：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int levelSize = q.size();
depth++;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return depth;
}
};
3.翻转二叉树
思路分析：这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
具体实现代码（详解版):
/**
* 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:
TreeNode* invertTree(TreeNode* root) {
// 1. 基础情况：如果当前节点为空，返回 nullptr。
if (!root) return nullptr;
// 2. 递归翻转当前节点的左子树，将翻转后的左子树的根节点存储在 left。
TreeNode* left = invertTree(root->left);
// 3. 递归翻转当前节点的右子树，将翻转后的右子树的根节点存储在 right。
TreeNode* right = invertTree(root->right);
// 4. 交换左右子树，使当前节点的左子树指向翻转后的右子树。
root->left = right;
// 5. 使当前节点的右子树指向翻转后的左子树。
root->right = left;
// 6. 返回当前节点（作为翻转后的树的根节点）
return root;
}
};
4.对称二叉树
思路分析：递归，如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
- 通过「同步移动」两个指针的方法来遍历这棵树，left指针和 right指针一开始都指向这棵树的根，随后 left 右移时，right 左移，left 左移时，right右移。每次检查当前left 和 right 节点的值是否相等，如果相等再判断左右子树是否对称。
具体实现代码（详解版）：
/**
* 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 isSymmetric(TreeNode* root) {
// 若根节点为空，直接认为是对称的
if (!root) return true;
// 使用递归检查左右子树是否镜像
return isMirror(root->left, root->right);
}
private:
bool isMirror(TreeNode* left, TreeNode* right) {
// 如果左右节点都为空，说明对称
if (!left && !right) return true;
// 如果只有一个节点为空，则不对称
if (!left || !right) return false;
// 两个节点值相同，且左节点的左子树与右节点的右子树对称，左节点的右子树与右节点的左子树对称
return (left->val == right->val) &&
isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
};
5.二叉树的直径
思路分析：递归法，左右子树高度之和就是经过当前节点的当前最大直径
具体实现代码（详解版）：
/**
* 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:
int diameterOfBinaryTree(TreeNode* root) {
// 初始化最大直径
int diameter = 0;
// 计算树的高度并更新直径
height(root, diameter);
return diameter;
}
private:
// 递归计算树的高度，并更新直径
int height(TreeNode* node, int& diameter) {
// 基础情况：如果当前节点为空，返回 0
if (!node) return 0;
// 递归计算左子树和右子树的高度
int leftHeight = height(node->left, diameter);
int rightHeight = height(node->right, diameter);
// 更新直径为左右子树高度之和
diameter = max(diameter, leftHeight + rightHeight);
// 返回当前节点的高度
return 1 + max(leftHeight, rightHeight);
}
};
