[剑指Offer]27-二叉树的镜像

题目链接

https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

输入一棵二叉树，输出它的镜像。

思路

前序遍历一遍，若遍历到的节点是非叶节点，就交换它的左右子节点。

相关

遇到数据结构相关问题，比如二叉树、数组、链表等，有画图分析的意识。
一些题目边界条件的处理也可从画图分析得到。

代码（Java）

原地版

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        if(root.left!=null||root.right!=null){
            TreeNode tmp=root.left;
            root.left=root.right;
            root.right=tmp;
        }

        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

新树版

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode node=new TreeNode(root.val);
        node.left=mirrorTree(root.right);
        node.right=mirrorTree(root.left);
        return node;
    }
}

代码（C++）

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot!=nullptr){
            if(pRoot->left!=nullptr||pRoot->right!=nullptr){
                TreeNode* pTemp=pRoot->left;
                pRoot->left=pRoot->right;
                pRoot->right=pTemp;

                if(pRoot->left!=nullptr){
                    Mirror(pRoot->left);
                }
                if(pRoot->right!=nullptr){
                    Mirror(pRoot->right);
                }
            }
        }

    }
};