38 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

理解题意，翻转即每个结点的左右子树翻转/对调

题解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) return nullptr;TreeNode* LEFT(nullptr), *RIGHT(nullptr);/** 递归思路：最后翻转的树 = 翻转后的左子树 + 翻转后的右子树有左子树，翻转左子树有右子树，翻转右子树每次翻转的步骤一致，所以符合递归思路**/if(root->left)LEFT = invertTree(root->left);if(root->right) RIGHT = invertTree(root->right);root->left = RIGHT;root->right = LEFT;return root;}
};

题解2 迭代——自上而下

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(! root) return nullptr;// 换成stack，按自上而下思路，逻辑一致queue<TreeNode*> Que;Que.push(root);while(Que.size()){TreeNode* tmp = Que.front();Que.pop();TreeNode* left = tmp->left;TreeNode* right = tmp->right;if(left) Que.push(left);if(right) Que.push(right);tmp->left = right;tmp->right = left;}return root;}
};