【剑指Offer】面试题27. 二叉树的镜像
2024-09-22 03:55:58
题目
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：
0 <= 节点个数 <= 1000
思路一：递归
自底向上。
代码
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (!root || (!root->left && !root->right)) return root;
root->left = mirrorTree(root->left);
root->right = mirrorTree(root->right);
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
return root;
}
};
另一种写法
自顶向下。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root) {
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
root->left = mirrorTree(root->left);
root->right = mirrorTree(root->right);
}
return root;
}
};
化简
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root) {
TreeNode *tmp = root->left;
root->left = mirrorTree(root->right);
root->right = mirrorTree(tmp);
}
return root;
}
};
思路二：迭代
层次遍历。
时间复杂度：O(n)
空间复杂度：O(n)
代码
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root) {
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
TreeNode *node = que.front();
que.pop();
TreeNode *tmp = node->left;
node->left = node->right;
node->right = tmp;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
最新文章
- 移动WEB开发之viewport
- Oracle12c IMO 测试
- js小知识归纳（待续）
- SVN-简要说明
- [JAVA] java_实例 获得系统字体
- uva 297 quadtrees——yhx
- MvcPager分页控件的使用
- 14款经典的MySQL客户端软件
- [BZOJ 1044] [HAOI2008] 木棍分割 【二分 + DP】
- Tab页签切换
- 帝国cms <!--list.var1-->,<!--list.var2-->的终极用法
- 团队项目(spring会议）
- sqlDependency监控数据库数据变化，自动通知
- 已有模板与tp框架结合
- PAT乙级-1043. 输出PATest(20)
- Django REST framework--序列化
- JS防抖与节流函数封装
- coursera-斯坦福-机器学习-吴恩达-笔记week2
- Pycharm2018的激活方法或破解方法（必须加host）
- mybatis源码解析5---SqlSession解析