1. 题目描述（简单难度）

[success] 226. 翻转二叉树

2. 解法一： 使用递归

我们从根节点开始，递归地对树进行遍历，并从叶子结点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root 为根节点的整棵子树的翻转。

class Solution {
    public TreeNode invertTree(TreeNode root) {
     if(root == null){
         return null;
     }
     TreeNode temp = root.left;
     root.left = root.right;
     root.right = temp;

     invertTree(root.left);
     invertTree(root.right);

     return root;
    }
}

3. 解法二： 使用队列进行 BFS

递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。 广度优先遍历需要额外的数据结构--队列，来存放临时遍历到的元素。 深度优先遍历的特点是一竿子插到底，不行了再退回来继续；而广度优先遍历的特点是层层扫荡。 所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。 对当前元素调换其左右子树的位置，然后：

• 判断其左子树是否为空，不为空就放入队列中
• 判断其右子树是否为空，不为空就放入队列中

class Solution {
    public TreeNode invertTree(TreeNode root) {
       Deque<TreeNode> deque = new LinkedList<>();
       deque.offer(root);
       while(!deque.isEmpty()){
            TreeNode curr = deque.poll();
            if(curr == null){
                continue;
            }
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;

            deque.offer(curr.left);
            deque.offer(curr.right);
       }
       return root;
    }
}