剑指27：二叉树的镜像

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    递归实现
*/
class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if (pRoot == nullptr) return nullptr;
        if (pRoot->left == nullptr && pRoot->right == nullptr) return pRoot;

        TreeNode* t = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = t;
        // swap(pRoot->left, pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};

/*
    迭代实现：使用队列，类似于层次遍历。
*/
class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if (pRoot == nullptr) return nullptr;
        
        queue<TreeNode*> q;
        q.push(pRoot);
        while (!q.empty()) {
            TreeNode* p = q.front();
            q.pop();
            if (p != nullptr) {
                q.push(p->left);
                q.push(p->right);
                // swap(p->left, p->right);
                TreeNode* t = p->left;
                p->left = p->right;
                p->right = t;
            }
        }
        return pRoot;
    }
};

C++ 代码 - leetcode

/*
    二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题可以使用两种思维模式。
*/

// 分解问题
class Solution {
public:
    // 函数定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        // 利用函数定义，先翻转左右子树
        TreeNode* left = mirrorTree(root->left);
        TreeNode* right = mirrorTree(root->right);
        // 然后交换左右子节点
        root->left = right;
        root->right = left;

        // 以 root 为根的这棵二叉树已经被翻转，返回 root
        return root;
    }
};

// 遍历
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        // 遍历二叉树，交换每个节点的子节点
        traverse(root);
        return root;
    }

    // 二叉树遍历函数
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        /**** 前序位置 ****/
        // 每一个节点需要的操作：交换它的左右子节点
        TreeNode* t = root->left;
        root->left = root->right;
        root->right = t;

        // 遍历框架，遍历左右子树的节点
        traverse(root->left);
        traverse(root->right);
    }
};