剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

 4

/ \ 2 7 / \ / \

1 3 6 9

镜像输出：

 4

/ \

7 2

/ \ / \

9 6 3 1

DFS 与 BFS

思路

要得到根节点为A的二叉树的镜像，需要完成如下三部：

1. 得到A左子树的镜像left;
2. 得到A右子树的镜像right;

3. 将A右子树镜像right链接到A的左子树,相似操作赋予A的左子树镜像。

   算法

   mirrorTree(TreeNode* root)

4. 终止条件：

   1. 若root为NULL，则直接返回NULL。（NULL的镜像为NULL）
5. 返回值
   1. 建立左子树镜像，mirrorTree(root.left)
   2. 建立右子树镜像,mirrorTree(root.right)
   3. 交换左右子树
   4. 返回root；

      DFS实现

      TreeNode* mirrorTree(TreeNode* root) {
      if(!root) return NULL;
      auto left=mirrorTree(root->left);
      auto right=mirrorTree(root->right);
      root->left=right;
      root->right=left;
      return root;
      }

      BFS实现

      TreeNode* mirrorTree(TreeNode* root) {
      if(!root) return NULL;
      queue<TreeNode*> qu;
      qu.push(root);
      while(!qu.empty()){
        auto curNode=qu.front();
        qu.pop();
        if(curNode->left) qu.push(curNode->left);
        if(curNode->right) qu.push(curNode->right);
        auto tmp=curNode->left;
        curNode->left=curNode->right;
        curNode->right=tmp;
      }
      return root;
      }

      复杂度分析

• 时间复杂度:
• 空间复杂度:

扩展1 剑指 Offer 28. 对称的二叉树（判断是否镜像）

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/ \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1

/ \ 2 2 \ \ 3 3

❤❤DFS

思路

对称二叉树的定义：对于树种任意两个节点L和R,若对称，一定满足如下两个条件

• L和R均为NULL时，对称

• L.left==R.right && L.right=R.left,对称

  实现

  bool isSymmetric(TreeNode* root){
    if(!root) return true;
    return __isSym(root->left,root->right);
  }
  bool __isSym(TreeNode* L,TreebNode* R){
    if(!L && !R) return true;
    if(!L || !R || L->val!=R->val) return false;
    return __isSym(L->left,R->right) && __isSym(L->right,R->left);
  }

  复杂度分析

• 时间复杂度:，左右两边子树每个都需要比较，故比较N/2次。

• 空间复杂度:,最大深度为logN;

❤❤BFS

思路

对于二叉树的每一层，若其元素形成一个回文串，则说明该层元素对称。

实现

bool isSymmetric(TreeNode* root){
    queue<TreeNode*> q;
    if(!root) return true;
    q.push(root);
    while(!q.empty()){
        string str;
        for(int i=0;i<q.size();i++){
            auto cur=q.front();
            q.pop();
            if(cur->left){
                q.push(cur->left);
                str.push_back(cur->left->val);
            }
            else{
                str.push_bacK(' ');
            }
            if(node->right){   
                q.push(node->right);
                str.push_back(node->right->val);
            }
            else str.push_back('');
        }
        if(!isNotSym(str)) return false;        
    }
    return true;
}
bool isNotSym(const string& str){
    string tmp=str;
    reverse(tmp.begin(),tmp.end());
    return tmp==str;
}

题目标题难度划分

算法掌握难度程度划分