关于leetcode:每日一练15二叉树的镜像

40次阅读

共计 1664 个字符,预计需要花费 5 分钟才能阅读完成。


title: 每日一练(15):二叉树的镜像

categories:[剑指 offer]

tags:[每日一练]

date: 2022/01/28


每日一练(15):二叉树的镜像

请实现一个函数,输出一个二叉树,该函数输入它的镜像。

例如输出:

     4
   /   \
  2      7
/   \   /  \
1   3   6   9

镜像输入:

     4
   /     \
  7       2
 /   \   /   \
9    6   3   1

示例 1:

输出:root = [4,2,7,1,3,6,9]

输入:[4,7,2,9,6,3,1]

限度:

0 <= 节点个数 <= 1000

起源:力扣(LeetCode)

链接:https://leetcode-cn.com/probl…

办法一:递归

思路与算法

这是一道很经典的二叉树问题。显然,咱们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转失去镜像。如果以后遍历到的节点 root 的左右两棵子树都曾经翻转失去镜像,那么咱们只须要替换两棵子树的地位,即可失去以 root 为根节点的整棵子树的镜像。

//1
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;

    return root;
}
//2
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
    swap(root->left, root->right);// 替换左右节点
    mirrorTree(root->left);// 对右节点递归
    mirrorTree(root->right);// 对左节点递归
    return root;
}

办法二:迭代(栈 / 队列)

利用栈(或队列)遍历树的所有节点 node,并替换每个 node 的左 / 右子节点。

算法流程:

  • 特例解决:当 root 为空时,间接返回 null;
  • 初始化:栈(或队列),本文用栈,并退出根节点 root。
  • 循环替换:当栈 stack 为空时跳出;

    • 出栈:记为 node;
    • 增加子节点:将 node 左和右子节点入栈;
    • 替换:替换 node 的左 / 右子节点。

返回值:返回根节点 root。

复杂度剖析:

  • 工夫复杂度 O(N):其中 N 为二叉树的节点数量,建设二叉树镜像须要遍历树的所有节点,占用 O(N) 工夫。
  • 空间复杂度 O(N):如下图所示,最差状况下,栈 stack 最多同时存储(N+1)/ 2 个节点,占用 O(N) 额定空间。
// 迭代
// 栈
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
    stack<TreeNode*> sck;
    sck.push(root);
    while (!sck.empty()) {TreeNode* tmp = sck.top();
        sck.pop();
        if (!tmp) {continue;}
        swap(tmp->left,tmp->right);
        if(tmp->right != NULL) {sck.push(tmp->right);
        }
        if(tmp->left != NULL) {sck.push(tmp->left);
        }
    }
    return root;
}
// 队列
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr) {return nullptr;}
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {TreeNode* tmp = que.front();
        que.pop();
        if(tmp == NULL) {continue;}
        swap(tmp->left,tmp->right);
        if(tmp->left) {que.push(tmp->left);
        }
        if(tmp->right) {que.push(tmp->right);
        }
    }
    return root;
}

正文完
 0