题解 | #二叉树的镜像#

二叉树的镜像

https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7

方法:递归

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

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;
    }
};

刷题题解(c++) 文章被收录于专栏

算法题题解(c++)

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务