题解 | #二叉树的镜像#

第十五题 将左右子树镜像

第一种方法 简单 直接复制一个新树

原先遍历为先序遍历根左右

现在构造新树逐个添加的点就是根右左

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* ret_ans;
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        // 第一种 直接遍历 直接造新树
        if(pRoot == NULL)
            return NULL;
        else
            ret_ans=new TreeNode(0);
        // 调用递归的复制函数
        copytree(pRoot, ret_ans);
        return ret_ans;
    }
    
    void copytree(TreeNode* pRoot,TreeNode* copy_tree)
    {
        if(pRoot == NULL)
            return;
        copy_tree->val=pRoot->val;
        // 递归调用 添加新的结点 有左子树 就调用左子树 / 有右子树 就调用右子树
        if( pRoot->left!=NULL )
        {
            copy_tree->right=new TreeNode(0);
            // 因为是镜像 原先是左边的 在构造的时候 构造到右边
            copytree(pRoot->left,copy_tree->right);
        }
        if(pRoot->right!=NULL)
        {
            copy_tree->left=new TreeNode(0);
            copytree(pRoot->right,copy_tree->left);
        }
        return;
    }
};

第二种方法 不复制新结点 需要思考一下

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // 第二种方法 不创建新的树的原地调换
        // 代码简单 但要考虑交换什么
        
        // 如果说是空节点 递归直接返回
        if(pRoot ==NULL)
            return NULL;
        
        // 将该节点的左右子树对调
        // 考虑以下几种情况：
        // 1.左右完全对称
        // 2.左边有树 但是右边缺了（镜像过去要在右边创建子树，并且删掉左边的子树）
        // 3.右边有 左边无 同上
        
        // 直接调用交换左右两边的孩子的结点
        TreeNode* temp = pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=temp;
        // 继续往下递归调用
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};