当前位置：首页 > news >正文

LeetCode 热题 100之二叉树

news 2024/11/1 16:29:09

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，这时完成左子树的遍历
访问跟根节点
- 从栈中弹出一个节点，将其值添加到结果数组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;  // 空节点深度为 0int 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) {// 基础情况：如果当前节点为空，返回 0if (!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);}
};