LeetCode HOT100系列题解之翻转二叉树（5/100）

标题：翻转二叉树. - 力扣（LeetCode）

题解：递归

标题很简朴，必要翻转全部得节点得左右子树。对于树类标题，我们固然起首思量递归。
在递归过程，我们要思量得停止条件，而这里得停止条件就是叶子节点。当节点为叶子节点时，其自己并不会举行翻转。而怎样举行翻转，实际上与swap函数同理，那么剩下只是一个递归过程。
思量到一棵树，有递归有四种情况：

• 无左孩子有右孩子：root->left 为 nullptr，root->rigtht 不为nullptr（只递归右侧）
  
• 无右孩子有左孩子：root->rigtht 为 nullptr，root->left 不为nullptr（只递归左侧）
  
• 左右孩子都有：root->left 、root->rigtht 均不为nullptr（递归左右侧）
  
• 左右孩子都无：root->left 、root->rigtht 均为nullptr（叶子节点，返回）
  

代码：

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     TreeNode* reverse(TreeNode* root)
15.     {
16.         if (root == nullptr) // 检查空指针
17.             return nullptr;
19.         if(root->left == nullptr && root->right == nullptr) //判断是否是叶子节点，直接返回
20.             return root;
21.    
22.         if(root->left != nullptr) reverse(root->left);
23.         if(root->right != nullptr) reverse(root->right);
24.            
26.         TreeNode* p = root->left;
27.         root->left = root->right;
28.         root->right = p;
30.         return root;
31.     }
32.     TreeNode* invertTree(TreeNode* root) {
33.         TreeNode* reverse_Tree = reverse(root);
35.         return reverse_Tree;
36.     }
37. };

复制代码

思考：对于树得递归

对于树得递归来说，我们只必要思量到叶子节点，大概上几层来举行模拟，来处置惩罚标题中举行过程得利用。剩下的只是判断左右子树是否递归，