简单
给你一棵二叉树的根节点 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; // 如果根节点为空,直接返回该节点,不进行翻转操作 stackst; // 创建一个栈,用于存储待翻转的节点 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) { queueque; // 创建一个队列,用于存储待翻转的节点 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; // 返回翻转后的根节点 } };以上是代码中的注释,解释了每一行代码的作用。
- 创建一个队列,用于存储待翻转的节点。
- 如果根节点不为空,则将根节点入队列。
- 使用迭代法进行翻转操作:
- 获取当前队列的大小,即当前层的节点数。
- 遍历当前层的节点:
- 取出队首节点作为当前节点。
- 交换当前节点的左右子树,实现翻转操作。
- 如果当前节点的左子树不为空,则将左子树节点入队列,准备进行翻转操作。
- 如果当前节点的右子树不为空,则将右子树节点入队列,准备进行翻转操作。
- 返回翻转后的根节点。
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。