AcWing 38. 二叉树的镜像

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 38. 二叉树的镜像原题链接简单

作者：

yxc , 2019-01-07 01:10:15 , 所有人可见 , 阅读 7082

29

10

算法

(二叉树，递归) $O(n)$

仔细观察原树和镜像之后的树：

我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换！

所以我们递归遍历原树的所有节点，将每个节点的左右儿子互换即可。

时间复杂度

原树仅被遍历一次，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void mirror(TreeNode* root) {
        if (!root) return;
        swap(root->left, root->right);
        mirror(root->left);
        mirror(root->right);
    }
};

26 评论

Bingxiu 2023-01-06 17:28

压行一下，只需一行
if(root) swap(root->left,root->right),mirror(root->left),mirror(root->right);

无情花花 2023-04-11 13:24

这是什么意思

Bingxiu 2023-04-15 18:42 回复了无情花花的评论

就是直接压行

古城萧笙 2023-09-18 12:30

6哦

XYL 2022-03-24 09:05

swip竟然能直接用

古城萧笙 2023-09-18 12:30

zdy5574 2022-03-01 16:04

class Solution {
public:
    void mirror(TreeNode* root) {
        root = build_mirror(root);
    }
    TreeNode* build_mirror(TreeNode* root){
        if(!root) return NULL;
        TreeNode* m_root = new TreeNode(root -> val);
        m_root -> left = build_mirror(root -> right);
        m_root -> right = build_mirror(root -> left);
        return m_root;
    }
};

为什么这么写不对呢，我感觉是能交换的啊，麻烦大佬解答一下疑惑

LSC_lsc 2022-05-01 19:28

你这只是把原根节点的指针指向了一个与源二叉树对称新的二叉树
但是源二叉树内存里的东西并没有改变

lwy911 2022-01-14 19:31

交换两个指针我这么写怎么不通过

class Solution {
public:
    void swapBranch(TreeNode* left,TreeNode* right){
        TreeNode* temp = left;
        left = right;
        right = temp;
        return;
    }
    void mirror(TreeNode* root) {
        if(!root || (!root->left && !root->right))  return;
        swapBranch(root->left,root->right);
        mirror(root->left);
        mirror(root->right);
        return;
    }
};

Moonlight 2022-02-18 16:25

用引用试试，或者二级指针。你这样写传参传的是拷贝，不会改变原来的值

曹亚洲 2021-04-16 17:39

第三层的应该是交换了上一层兄弟节点的左右节点啊，6节点的左子树5和10节点的右子树11交换的，还有循环第一次后8的左节点是10，右节点是6，那么此时第三层是什么样子呢？表示不理解

Komorebi_29 2021-07-20 15:48

递归执行，先交换下层，交换完再交换上层。建议写个递归二叉树看看

_M_ 2022-02-09 00:00 回复了 Komorebi_29 的评论

先序递归先交换的上层他直接交换了指针所以先序和后序都可以

Scathon 2021-03-08 18:53

第一次和y总写出一模一样的代码。。。。。。

Scathon 2021-03-20 22:16

提供一个循环的写法，供大家参考，其实就是层次遍历：）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void mirror(TreeNode* root) {
        if (!root) return;
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty())
        {
            int sz = q.size();
            while (sz--)
            {
                auto t = q.front();
                swap(t->left, t->right);
                if (t->left) q.push_back(t->left);
                if (t->right) q.push_back(t->right);
                q.pop_front();
            }
        }
    }
};