题解 | 二叉树的镜像

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
lass Solution {
  public:
    /**
     * 递归实现二叉树镜像变换 - void返回类型
     * 时间复杂度：O(n)，空间复杂度：O(n)（递归栈空间）
     */
    
    TreeNode* Mirror(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        // 递归处理左右子树
        TreeNode* leftMirror = Mirror(root->left);
        TreeNode* rightMirror = Mirror(root->right);

        // 交换左右子树（原地修改）
        root->left = rightMirror;
        root->right = leftMirror;

        return root;
    }
};

1.其实在原地修改可以使用void函数类型
2.可以先递归后交换也可以先交换后递归
3.先交换后递归是从上往下交换的,先递归后交换是从下往上交换的