226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

输出：

思路一：递归

直接进行递归，交换左右孩子后，对左右孩子分别递归交换左右孩子

 1 class Solution {
 2     public TreeNode invertTree(TreeNode root) {
 3         // 如果根节点为null, 直接返回null
 4         if(root == null){
 5             return null;
 6         }
 7         // 交换root的左右子树
 8         TreeNode temp = root.left;
 9         root.left = root.right;
10         root.right = temp;
11         // 递归交换左右子树
12         invertTree(root.left);
13         invertTree(root.right);
14         return root;
15     }
16 }

复杂度分析

时间复杂度：需要对每个结点进行一次递归，所以时间复杂度为O(n), n等于结点个数

空间复杂度：每次递归都需要一个临时变量temp， 但是这是常数级别的，最大递归深度为树的高度，所以复杂度为O(h)， 由于树的平衡性未知，所以空间复杂度为O(n) 而不是O(logn)

思路二：BFS

利用BFS遍历结点，在每次弹出队首结点时，将结点的左右孩子进行交换，然后入队左右孩子

 1 class Solution {
 2     public TreeNode invertTree(TreeNode root) {
 3         // 利用BFS遍历结点，在每次弹出队首结点时，将结点的左右孩子进行交换，然后入队左右孩子
 4         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 5         if(root == null)
 6             return null;
 7         queue.offer(root);
 8         while(!queue.isEmpty()){
 9             TreeNode top = queue.poll();
10             TreeNode temp = top.left;
11             top.left = top.right;
12             top.right = temp;
13             if(top.left != null)
14                 queue.offer(top.left);
15             if(top.right != null)
16                 queue.offer(top.right);
17         }
18         return root;
19     }
20 }

复杂度分析

时间复杂度：同思路一一样，都是对树的每个结点进行了一次访问，所以时间复杂度为O(n)

空间复杂度：队列中只会存储一层的结点，所以最坏情况下，对于一颗完整二叉树来说，叶子节点那一层拥有⌈n/2​⌉=O(n) 个节点。

思路来源：

https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode/