题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目范围在 [0, 100] 内
- -100 <= Node.val <= 100
解题思路
其实就是交换一下每一个节点的左右孩子。
这道题目使用前序、后序都可以，中序会将一些节点翻转两次。
这里使用前序遍历。
递归法
递归三部曲：
确定递归函数的参数和返回值
参数就是传入节点的指针，题目要求返回其根节点，因此可以用其提供的TreeNode*TreeNode* invertTree(TreeNode root)确定递归函数的终止条件
当节点为空，递归终止。if (root == NULL) return root;确定递归的逻辑
前序遍历：中左右。先交换左右孩子节点，然后反转左子树，反转右子树。swap(root.left, root.right); invertTree(root->left); invertTree(root->right);
迭代法
深度优先遍历
模板题，注意交换逻辑即可。
广度优先遍历（层次遍历）
模板题，注意交换逻辑即可。
代码实现
递归法
// 前序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root.left, root.right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
迭代法
深度优先遍历
// 前序遍历：中左右
// 入栈顺序：右左中
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (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();
swap(node->left, node->right);
}
}
return root;
}
};
广度优先遍历（层次遍历）
// 前序遍历：中左右
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();
swap(node->left, node->right);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
