题⽬描述

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

⼆叉树的镜像定义：源⼆叉树

思路及解答

递归

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

  1. 递归处理左子树

  2. 递归处理右子树

  3. 访问根节点并交换其左右子树

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

  1. 访问根节点并交换其左右子树

  2. 递归处理左子树

  3. 递归处理右子树

  • 时间复杂度​：O(n)，每个节点只被访问一次

  • 空间复杂度​：O(h)，h为树的高度，递归栈空间消耗

迭代

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

  1. 将根节点加入队列

  2. 取出队首节点并交换其左右子树

  3. 将非空的左右子节点加入队列

  4. 重复直到队列为空

  • 时间复杂度​：O(n)

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