剑指offer：二叉树的镜像

剑指offer：二叉树的镜像

文章目录

• • • 分析
    • 题目来源

分析

思路：

可以发现，对于任意一个结点来说，左孩子和右孩子（只要有的话）都是互换的。

时间复杂度：O（n），每个结点遍历一遍

ac代码

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        // 交换左右孩子(这里空指针也参与交换，因为swap交换的是指针)
        swap(root->left, root->right);
        // 递归遍历即可
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

题目来源

https://www.acwing.com/problem/content/37/