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

力扣第226翻转二叉数 c++三种方法＋注释

news 2025/7/12 8:59:26

题目

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

c++ 代码一（递归法）
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;  // 如果根节点为空，直接返回该节点，不进行翻转操作swap(root->left, root->right);  // 交换当前节点的左右子树，实现翻转操作invertTree(root->left);         // 递归地对当前节点的左子树进行翻转invertTree(root->right);        // 递归地对当前节点的右子树进行翻转return root;                    // 返回翻转后的根节点}
};
以上是代码中的注释，解释了每一行代码的作用。

如果根节点为空，直接返回根节点，不进行翻转操作。
交换当前节点的左右子树，实现翻转操作。
递归地对当前节点的左子树进行翻转。
递归地对当前节点的右子树进行翻转。
返回翻转后的根节点。

c++ 代码二（迭代法（前序遍历））
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;  // 如果根节点为空，直接返回该节点，不进行翻转操作stack<TreeNode*> st;  // 创建一个栈，用于存储待翻转的节点st.push(root);        // 将根节点入栈while (!st.empty()) {TreeNode* node = st.top();  // 取出栈顶节点作为当前节点st.pop();swap(node->left, node->right);  // 交换当前节点的左右子树，实现翻转操作if (node->right) st.push(node->right);  // 如果当前节点的右子树不为空，则将右子树节点入栈，准备进行翻转操作if (node->left) st.push(node->left);    // 如果当前节点的左子树不为空，则将左子树节点入栈，准备进行翻转操作}return root;  // 返回翻转后的根节点}
};
以上是代码中的注释，解释了每一行代码的作用。

如果根节点为空，直接返回根节点，不进行翻转操作。
创建一个栈，用于存储待翻转的节点。
将根节点入栈。
使用迭代法进行翻转操作：
取出栈顶节点作为当前节点。
交换当前节点的左右子树，实现翻转操作。
如果当前节点的右子树不为空，则将右子树节点入栈，准备进行翻转操作。
如果当前节点的左子树不为空，则将左子树节点入栈，准备进行翻转操作。
返回翻转后的根节点。

c++ 代码三（广度优先遍历）
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;  // 创建一个队列，用于存储待翻转的节点if (root != NULL) que.push(root);  // 如果根节点不为空，则将根节点入队列while (!que.empty()) {  // 当队列不为空时循环执行操作int size = que.size();  // 获取当前队列的大小，即当前层的节点数for (int i = 0; i < size; i++) {  // 遍历当前层的节点TreeNode* node = que.front();  // 取出队首节点作为当前节点que.pop();  // 出队列swap(node->left, node->right);  // 交换当前节点的左右子树，实现翻转操作if (node->left) que.push(node->left);  // 如果当前节点的左子树不为空，则将左子树节点入队列，准备进行翻转操作if (node->right) que.push(node->right);  // 如果当前节点的右子树不为空，则将右子树节点入队列，准备进行翻转操作}}return root;  // 返回翻转后的根节点}
};
以上是代码中的注释，解释了每一行代码的作用。

创建一个队列，用于存储待翻转的节点。
如果根节点不为空，则将根节点入队列。
使用迭代法进行翻转操作：
获取当前队列的大小，即当前层的节点数。
遍历当前层的节点：
取出队首节点作为当前节点。
交换当前节点的左右子树，实现翻转操作。
如果当前节点的左子树不为空，则将左子树节点入队列，准备进行翻转操作。
如果当前节点的右子树不为空，则将右子树节点入队列，准备进行翻转操作。
返回翻转后的根节点。