二叉树应用_二叉树镜像（对称）

- 日理万妓 2022-05-22 02:42 233阅读 0赞

题目：完成一个函数，输入一个二叉树，该函数输出它的镜像。  
如：  
![这里写图片描述][70]  
分析：对于一个二叉树的镜像过程，我们可以先前序遍历这棵树的每一个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有的飞叶子节点之后，就得到了树的镜像。  
具体实现：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    void MirrorRecursively(TreeNode *pnode)
    {
        if(pnode==NULL)
            return;
        if(pnode->right==NULL&&pnode->left==NULL)
            return;
        TreeNode *ptemp=pnode->left;
        pnode->left=pnode->right;
        pnode->right=ptemp;
        if(pnode->left)
            MirrorRecursively(pnode->left);
        if(pnode->right)
            MirrorRecursively(pnode->right);
    }

题目：实现一个函数，判断一课二叉树是不是对称的。如果一个二叉树和他的镜像是完全一样的，那么它就是对称的。  
分析：两种遍历方式：根、左、右；根、右、左；当这两种遍历得到的序列是一样的就认为时对称的二叉树。此外还应该考虑把遍历遇到的NULL指针也考虑进来（处理全部节点一样的情况）

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
     bool isSymmetrical(TreeNode* pRoot1,TreeNode* pRoot2)
     {
         if(!pRoot1&&!pRoot2)
             return true;
    
         if(!pRoot1||!pRoot2)
             return false;
    
         if(pRoot1->val!=pRoot2->val)
             return false;
    
         return isSymmetrical(pRoot1->left,pRoot2->right)&&isSymmetrical(pRoot1->right,pRoot2->left);
     }
    bool isSymmetrical(TreeNode*proot)
    {
        return isSymmetrical(proot,proot);
    }

[70]: /images/20220522/b2290c75298745e0b51f13c9b1d0b33f.png