核心考点 ：二叉树操作。
一、《剑指Offer》内容
二、分析题目
操作给定的二叉树，将其变换为源二叉树的镜像。仔细观察可以发现，所谓的二叉树镜像本质是自顶向下（或 自底向上） 进行左右子树交换的过程。 这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
三、代码
1、递归法
（1）前序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return nullptr; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; } };
（2）中序遍历（不推荐）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return root; invertTree(root->left); swap(root->left, root->right); invertTree(root->left); //注意细节 return root; } };
（3）后序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return root; invertTree(root->left); invertTree(root->right); swap(root->left, root->right); return root; } };
2、迭代法
（1）层序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: queue<TreeNode*> q; public: TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return root; q.push(root); while(q.size()) { int n=q.size(); while(n--) { TreeNode* node=q.front(); q.pop(); swap(node->left, node->right); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } } return root; } };
四、扩展
前面的代码是用递归实现的。如果要求用循环，该如何实现？
其实就是 2、迭代法中用到的层序遍历，这里就没有用到递归，而是利用队列先进先出的性质来实现的。
