[AcWing]38. 二叉树的镜像

输入一个二叉树，将它变换为它的镜像。

数据范围

树中节点数量 [0,100]。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入树：
      8
     / \
    6  10
   / \ / \
  5  7 9 11

 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
输出树：
      8
     / \
    10  6
   / \ / \
  11 9 7  5

 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

算法思路

仔细观察发现，镜像就是：交换左右子树，对于子树中的左右子节点也进行交换。
利用这个性质，抽象一下就是：递归遍历这个树，交换其左右子树。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void mirror(TreeNode* root) {
        // 递归到空的节点，就跳出，什么也不做
        if(!root) return;
        // 交换左右子树
        mirror(root -> left);
        mirror(root -> right);
        swap(root -> left, root -> right);
    }
};

上面的代码虽然简单，但还是可以分析一下。

  1. 从宏观上来看：这是个交换左右子树的过程。
  2. 从微观上来看：这是个先找到叶子结点，从下面开始交换左右节点的过程。（函数递归调用栈）

时间复杂度

原树仅被遍历一次，所以时间复杂度是 O(n)。