題目

翻轉一棵二叉樹。

示例：

輸入：

 4

/
2 7
/ \ /
1 3 6 9
輸出：
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) {queue<TreeNode*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i =0;i<size;i++){TreeNode* node = que.front();que.pop();TreeNode* tmp;tmp = node->left;node->left = node->right;node->right = tmp;//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return root;}
};

2、遞歸法：

遍歷的過程中去翻轉每一個結點的左右孩子就可以達到整體翻轉的效果。
可以使用先序遍歷和后序遍歷，而中序遍歷會把某些結點的左右孩子翻轉兩次。

1、先序遍歷（中左右）

遞歸思考過程：
1、返回值：void 形參：指向結點的指針
2、終止條件：指向結點的指針為空指針
3、遞歸內部邏輯：先翻轉指針指向的結點的左右孩子，然后遞歸遍歷左右子樹

/*** 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:void traversal(TreeNode* cur){//終止條件if(cur == NULL) return;//邏輯:先交換左右子樹內容，然后對左右子樹依次進行遍歷TreeNode* tmp;tmp = cur->left;cur->left = cur->right;cur->right = tmp;traversal(cur->left);traversal(cur->right);}TreeNode* invertTree(TreeNode* root) {traversal(root);return root;}
};

2、后序遍歷（左右中）

遞歸思考過程：
1、返回值：void 形參：指向結點的指針
2、終止條件：指向結點的指針為空指針
3、遞歸內部邏輯：先遞歸遍歷左右子樹，再翻轉指針指向的結點的左右孩子

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
/*** 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:void traversal(TreeNode* cur){//終止條件if(cur == NULL) return;traversal(cur->left);traversal(cur->right);TreeNode* tmp;tmp = cur->left;cur->left = cur->right;cur->right = tmp;}TreeNode* invertTree(TreeNode* root) {traversal(root);return root;}
};

為什么后序遍歷的方法更加快捷？

3、遞歸中序遍歷為什么不行（左中右）

中序遍歷之后是這樣的：

因為交換完左右結點后，想要遍歷右子樹，實際由于進行了交換操作，遍歷的還是原來的左子樹。
如下圖：

3、迭代法：

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) {stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加右結點if(node->right) st.push(node->right);//添加左結點if(node->left) st.push(node->left);//添加中結點st.push(node);//標記st.push(NULL); }//只有遇到空結點的時候，才將下一個結點的左右子結點進行交換else{//彈出空結點st.pop();node = st.top();st.pop();   TreeNode* tmp;tmp = node->left;node->left = node->right;node->right = tmp;}}return root;}
};

2、中序遍歷

/*** 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) {stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加右結點if(node->right) st.push(node->right);//添加中結點st.push(node);//標記st.push(NULL); //添加左結點if(node->left) st.push(node->left);}//只有遇到空結點的時候，才將下一個結點的左右子結點進行交換else{//彈出空結點st.pop();node = st.top();st.pop();   TreeNode* tmp;tmp = node->left;node->left = node->right;node->right = tmp;}}return root;}
};

3、后序遍歷

/*** 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) {stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加中結點st.push(node);//標記st.push(NULL); //添加右結點if(node->right) st.push(node->right);//添加左結點if(node->left) st.push(node->left);}//只有遇到空結點的時候，才將下一個結點的左右子結點進行交換else{//彈出空結點st.pop();node = st.top();st.pop();   TreeNode* tmp;tmp = node->left;node->left = node->right;node->right = tmp;}}return root;}
};

為什么迭代法的中序遍歷有效？

迭代的中序方法可以，因為先將交換前的右子樹值存放到棧內了，即使后面進行了交換，想要遍歷右子樹時，是取棧內交換前的右子樹值，而不是交換后的。
如圖：