二叉树的镜像

---

题目：

题解：

1、辅助队列（或栈）

• 解题思路：利用队列（或栈）遍历树的所有节点 poll，并交换每个 poll 的左 / 右子节点。

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
  • 空间复杂度 O(N) ： 如下图所示，最差情况下，队列 最多同时存储 (N+1)/ 2个节点，占用 O(N) 额外空间。

• 代码：

  class Solution {
      public TreeNode mirrorTree(TreeNode root) {
          if (root == null) {
              return null;
          }
  
          // 初始化队列
          Queue<TreeNode> queue  = new LinkedList() {{ add(root); }};
          while (!queue.isEmpty()) {
  
        
                  TreeNode poll = queue.poll();
  
                  if (poll.left != null) {
                      queue.add(poll.left);
                  }
                  if (poll.right != null) {
                      queue.add(poll.right);
                  }
                  // 将左右子节点的位置交换
                  TreeNode tmp = poll.left;
                  poll.left = poll.right;
                  poll.right = tmp;
              
  
          }
  
          return root;
      }
  }

2、递归法

• 解题思路：根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N)时间。
  • 空间复杂度 O(N) ： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间。

• 代码：

  class Solution2 {
      public TreeNode mirrorTree(TreeNode root) {
          if (root == null) {
              return null;
          }
  
          // 通过递归交换子结点的位置
          TreeNode tmp = root.left;
          root.left = mirrorTree(root.right);
          root.right = mirrorTree(tmp);
  
          return root;
      }
  }