题目要求
倒置一个二叉树，可以尝试递归和非递归方法。
输入示例
Input: 4/ \2 7/ \ / \
1 3 6 9Output:4/ \7 2/ \ / \
9 6 3 1
解题思路
通过输入的实例，我们可以发现，实际上倒置一个二叉树就是将树中每一个节点的左右孩子进行交换。
1、递归
因此，我们可以对每个节点的左右孩子进行记录，然后互换，递归的对每个节点进行执行即可，根据这个思想可以写出递归的主要代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return NULL;TreeNode* left = invertTree(root->left); // 记录左孩子TreeNode* right = invertTree(root->right); // 记录右孩子// 进行交换操作root->left = right;root->right = left;return root;}
};
2、非递归
非递归的实现需要我们利用队列的特性（先进先出FIFO）来完成操作。具体执行的时候是把根节点放入队列，然后读取队列的首元素(除了叶子节点外就是双亲节点)，然后交换这个元素的左右孩子，随后将交换后的左右孩子放入队列重复上面的操作，直到队列里面没有元素为止。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return NULL;queue<TreeNode*> q;q.push(root); // 根节点入队 操作开始while(!queue.empty()) // 队列中有元素的时候 重复以下操作{
TreeNode* cur = q.front(); q.pop();swap(cur->left,cur->right); // 交换双亲节点的左右孩子if(cur->left != NULL) q.push(cur->left); // 交换后的左孩子入队if(cur->right != NULL) q.push(cur->right); // 交换后的右孩子入队}return root; }
};
总结
正如以前说过的，在解决树类的大多数问题上，递归能迅速的给我们提供一个简单的解题思路，所以可以多用递归的思想去思考这类问题，特别的在进行二叉树的倒置，交换等操作的时候，队列是我们常用的辅助手段（排序是用栈），所以对队列不熟悉的朋友，要多多练习，记住我们常用的操作，和STL中的一些技巧。
入列：queue.push()
出列：queue.pop() 也是要率先指到队首元素（和栈一样），并不会返回值
队首元素：queue.front()，即最先被压入队列的元素
队尾元素：queue.back()，即最后被压入队列的元素
判断队列为空：queue.empty()
相似题目：
解答：leetcode 654. Maximum Binary Tree(构建最大二叉树)