题解 | #二叉树的镜像#

方法：递归

二叉树的镜像就是将二叉树的每个结点都交换它的左右子结点。

1、交换根结点的左右子结点；

2、进入左子树和右子树不断地向下交换根结点的左右子结点。

时间复杂度：o(n)

空间复杂度：o(n)，递归栈的深度。

class Solution {
  public:
    TreeNode* Mirror(TreeNode* pRoot) {
	  	//结点为空时，返回nullptr
        if (pRoot == nullptr)
            return nullptr;
		//交换根结点的左右子结点
        TreeNode* temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
		//不断向下递归，交换结点的左右子结点
        Mirror(pRoot->left);
        Mirror(pRoot->right);

        return pRoot;
    }
};

方法二：辅助队列

利用辅助队列，层序遍历不断交换结点的左右子结点。

时间复杂度：o(n)

空间复杂度：o(n)，递归栈的深度。

class Solution {
  public:
    TreeNode* Mirror(TreeNode* pRoot) {
        //结点为空，返回nullptr
        if (pRoot == nullptr)
            return nullptr;

        queue<TreeNode*> temp;
        temp.push(pRoot);
        //层序遍历，不断交换左右子结点
        while (!temp.empty()) {
            TreeNode* right = temp.front()->right;
            temp.front()->right = temp.front()->left;
            temp.front()->left = right;

            if (temp.front()->left != nullptr)
                temp.push(temp.front()->left);
            if (temp.front()->right != nullptr)
                temp.push(temp.front()->right);

            temp.pop();
        }
        return pRoot;
    }
};