1.题目

2.思路

基础递归题。
可以直接后序遍历（前序也可），递归到底后就交换左右孩子（叶结点），再往二叉树上返回。

前序和后序唯一的区别是：
前序遍历：将「处理当前节点」放到「递归左子树」之前。
后序遍历：将「处理当前节点」放到「递归右子树」之后。

3.代码

/**
 * 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==NULL){
            return root;//遍历到null节点时，不用翻转，直接返回它本身
        }
        TreeNode* leftchild=invertTree(root->left);
        TreeNode* rightchild=invertTree(root->right);
        root->left=rightchild;
        root->right=leftchild;
        return root;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

4.复杂度

（1）时间复杂度：$O(N)$，遍历每个结点（N个结点）。
（2）空间复杂度：$O(logN)$，递归栈高度即二叉树高度。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/115794445