剑指offer-18、⼆叉树的镜像

题⽬描述

操作给定的⼆叉树，将其变换为源⼆叉树的镜像。
⼆叉树的镜像定义：源⼆叉树

思路及解答

递归

采用后序遍历（左-右-根）的方式递归访问每个节点：

• 递归处理左子树
  
• 递归处理右子树
  
• 访问根节点并交换其左右子树
  

1. public TreeNode mirrorTree(TreeNode root) {
2.     if (root == null) return null;
3.     // 先递归处理子树
4.     TreeNode left = mirrorTree(root.left);
5.     TreeNode right = mirrorTree(root.right);
6.     // 再交换左右子树
7.     root.left = right;
8.     root.right = left;
9.     return root;
10. }

复制代码

或者采用前序遍历（根-左-右）的方式递归访问每个节点：

• 访问根节点并交换其左右子树
  
• 递归处理左子树
  
• 递归处理右子树
  

1. public TreeNode mirrorTree(TreeNode root) {
2.     if (root == null) {
3.         return null;
4.     }
5.     // 交换左右子树
6.     TreeNode temp = root.left;
7.     root.left = root.right;
8.     root.right = temp;
9.     // 递归处理左右子树
10.     mirrorTree(root.left);
11.     mirrorTree(root.right);
12.     return root;
13. }

复制代码

• ​时间复杂度​：O(n)，每个节点只被访问一次
  
• ​空间复杂度​：O(h)，h为树的高度，递归栈空间消耗
  

迭代

利用队列实现广度优先搜索(BFS)：

• 将根节点加入队列
  
• 取出队首节点并交换其左右子树
  
• 将非空的左右子节点加入队列
  
• 重复直到队列为空
  

1. public TreeNode mirrorTree(TreeNode root) {
2.     if (root == null) return null;
3.     Queue<TreeNode> queue = new LinkedList<>();
4.     queue.offer(root);
5.     while (!queue.isEmpty()) {
6.         TreeNode node = queue.poll();
7.         // 交换左右子树
8.         swap(node);
9.         // 将子节点加入队列
10.         if (node.left != null) queue.offer(node.left);
11.         if (node.right != null) queue.offer(node.right);
12.     }
13.     return root;
14. }
16. public void swap(TreeNode root) {
17.     TreeNode temp = root.left;
18.     root.left = root.right;
19.     root.right = temp;
20. }

复制代码

• 时间复杂度​：O(n)
  
• ​空间复杂度​：O(n)，最坏情况下需要存储所有节点
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！