Leetcode刷题技巧

1.Deque 双端队列
- 1.1 在java中为什么使用Deque，而不使用Stack呢？
- 1.2 ArrayDeque与LinkList区别：
  - ArrayDeque：
  - LinkList：
2.数组相关
4.树相关

1.Deque 双端队列

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

Deque有三种用途：

普通队列(一端进另一端出) Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出) Deque deque = new LinkedList()
堆栈 Deque deque = new LinkedList()

Deque是一个线性collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

	第一个元素 (头部)		最后一个元素 (尾部)
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst(e)	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。

1.1 在java中为什么使用Deque，而不使用Stack呢？

Stack实现了Vector接口，LinkKist实现了Deque,List接口，ArrayDeque实现了Deque接口。

为什么不推荐使用Stack呢？

因为Vector是当初JAVA曾经写得不太行的类，所以Stack也不太行。

Vector不行是因为效率不太行，很多方法都用了synchronized修饰，虽然线程安全，但是像ArrayDeque,LinkedList这些线程不安全的，在需要安全的时候也可以用Collections.synchronizedCollection()转化成线程安全的，所以Vector就没什么用处了

再根据仿生学
Stack只能上进上出，有点像刺胞动物（腔肠动物），就是那种从哪里吃进去就哪里拉出来的那种生活在海洋里的比较低级的生物。
Deque上进上出，上进下出，甚至下进上出，非常上流，只有你想不到，没有我Deque做不到的。

现在不会还有人不知道使用栈的时候选谁吧？

1.2 ArrayDeque与LinkList区别：

ArrayDeque：

数组结构
插入元素不能为null
无法确定数据量时，后期扩容会影响效率

LinkList：
链表结构
插入元素能为null
无法确定数据量时，有更好表现

2.数组相关

几数之和

总结，看到形如：A+B….+N=0的式子，要转换为(A+…T)=-((T+1)…+N)再计算，这个T的分割点一般是一半，特殊情况下需要自行判断。定T是解题的关键。

二分查找

题目链接：https://leetcode-cn.com/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

1.1 思路
这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
下面我用这两种区间的定义分别讲解两种不同的二分写法。

1.2 二分法第一种写法
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：
Leetcode刷题技巧 - 图2
代码如下：（详细注释）

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

1.3 二分法第二种写法
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
有如下两点：

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

在数组：1,2,3,4,7,9,10中查找元素2，如图所示：（注意和方法一的区别）
Leetcode刷题技巧 - 图3
代码如下：（详细注释）

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)  
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

1.4 二分法控制方向[向左/向右]

while (left <= right){
    int mid = left + (right - left) / 2;
    if (nums[mid] < target)
        left = mid + 1;
    else if (nums[mid] > target)
        right = mid - 1;
    else {
        res = mid;
        if (leftOrRight)
            right = mid - 1;
        else
            left = mid + 1;
    }
}

向左走则leftOrRight = true ，反之则为false。

删除数组元素(双指针模板)

移除元素
题目地址：https://leetcode-cn.com/problems/remove-element/
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
示例
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
2.1 思路
先设定变量 start，指向待插入位置。idx 初始值为 0
然后从题目的「要求/保留逻辑」出发，来决定当遍历到任意元素 nums[i] 时，应该做何种决策：

如果当前元素 nums[i]与移除元素 val 相同，那么跳过该元素。
如果当前元素 nums[i] 与移除元素 val 不同，那么我们将其放到下标start的位置，并让 idx 自增右移。
最终得到的 start即是答案。

2.2 过程图

起初start = 0，i = 0，需要删除元素值为2。扫描到的第一项为0 ，nums[i] != 2，则nums[start] = nums[i]

2.扫描到值为2的元素，则start不变，i继续后移，寻找非2的元素。

3.扫描到非2的元素，则nums[start] = nums[i]，赋值后start++。

2.3 讲解视频
链接：https://www.bilibili.com/video/BV1Pv4y1Z76N?from=search&seid=1036536317008860814
2.4 源码

package array;
public class Problem27 {
    public int removeElement(int[] nums, int val) {
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val){
                nums[start] = nums[i];
                start++;
            }
        }
        return start;
    }
}

如何递归反转链表

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的reverse函数定义是这样的：
输入一个节点**head**，将「以**head**为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：

那么输入reverse(head)后，会在这里进行递归：

ListNode last = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

按照定义，这个reverse(head.next)执行完成后，整个链表应该变成了这样：

并且根据函数定义，reverse函数会返回反转之后的头结点，我们用变量last接收了。
现在再来看下面的代码：

head.next.next = head;

接下来进行的操作：

head.next = null;
return last;

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：
1、递归函数要有 base case，也就是这句：

if (head.next == null) return head;

意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。
2、当链表递归反转之后，新的头节点是**last**，而之前的**head**变成了最后一个节点，别忘了链表的末尾要指向 null：

head.next = null;

如何反转某个节点之后的链表

ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

4.树相关

94.二叉树的中序遍历

1.递归实现
前序遍历：打印 - 左 - 右
中序遍历：左 - 打印 - 右
后序遍历：左 - 右 - 打印
题目要求的是中序遍历，那就按照左-打印-右这种顺序遍历树就可以了，递归函数实现

终止条件：当前节点为空时
函数内：递归的调用左节点，打印当前节点，再递归调用右节点
时间复杂度：O(n)
空间复杂度：O(h)，h是树的高度

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(res,root);
        return res;
    }
    void dfs(List<Integer> res, TreeNode root) {
        if(root==null) {
            return;
        }
        //按照 左-打印-右的方式遍历
        dfs(res,root.left);
        res.add(root.val);
        dfs(res,root.right);
    }
}

2.迭代实现
递归实现时，是函数自己调用自己，一层层的嵌套下去，操作系统/虚拟机自动帮我们用栈来保存了每个调用的函数，现在我们需要自己模拟这样的调用过程。

递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。
我们在迭代实现时，就可以用栈来模拟上面的调用过程。

Leetcode刷题技巧 - 图13
时间复杂度：O(n)
空间复杂度：O(h)，h是树的高度

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(stack.size()>0 || root!=null) {
            //不断往左子树方向走，每走一次就将当前节点保存到栈中
            //这是模拟递归的调用
            if(root!=null) {
                stack.add(root);
                root = root.left;
            //当前节点为空，说明左边走到头了，从栈中弹出节点并保存
            //然后转向右边节点，继续上面整个过程
            } else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }
}

3.莫里斯遍历
用递归和迭代的方式都使用了辅助的空间，而莫里斯遍历的优点是没有使用任何辅助空间。
缺点是改变了整个树的结构，强行把一棵二叉树改成一段链表结构。

Leetcode刷题技巧 - 图14

我们将黄色区域部分挂到节点5的右子树上，接着再把2和5这两个节点挂到4节点的右边。这样整棵树基本上就变改成了一个链表了，之后再不断往右遍历。

Leetcode刷题技巧 - 图15

时间复杂度:找到每个前驱节点的复杂度是 O(n)，因为 nn 个节点的二叉树有 n−1 条边，每条边只可能使用 2 次(一次定位到节点，一次找到前驱节点)，故时间复杂度为 O(n)
空间复杂度：O(1)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode pre = null;
        while(root!=null) {
            //如果左节点不为空，就将当前节点连带右子树全部挂到
            //左节点的最右子树下面
            if(root.left!=null) {
                pre = root.left;
                while(pre.right!=null) {
                    pre = pre.right;
                }
                pre.right = root;
                //将root指向root的left
                TreeNode tmp = root;
                root = root.left;
                tmp.left = null;
            //左子树为空，则打印这个节点，并向右边遍历    
            } else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

注：

TreeNode tmp = root;
root = root.left;
tmp.left = null;

在执行这段之前，根节点和右子树已经挂到左子树的最下面了

也就是把1-3-5这挂到2的右边，挂完之后开始下一轮处理

挂完之后，2的子节点就是1-3-5，这时候1的左节点2还没断开

所以此刻1还是2的父节点，于是就形成环了，这步就是要把环给断开。

103.二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：
[
  [3],
  [20,9],
  [15,7]
]

广度优先搜索算法+双端队列

这个和之前的层次遍历在于，它的遍历顺序是z型的。这就决定了用原来队列的方法行不通。但是可以这个基础上改。还是用双向队列来遍历整棵树。
将队列看成两个栈，前面的栈从前面进前面出。后面的栈从后面进后面出。每个栈中放每一层的所有节点，这些节点出栈，将他们的子树节点进入另一个栈。
先左后右子节点进入前面栈，先右后左节点进入后面栈。

实现：
1、判断是否为空
2、将根节点从前面加入到dequeue中。dequeue.addFirst().定义计数从0开始
3、循环遍历树直到dequeue为空
4、定义list，获取队列大小size，for循环size次。
5、判断计数是否是偶数。偶数的话从前面的栈获取元素。
6、将当前节点值放到list中。依次将非空的左子树，右子树节点放到后面栈中。
7、如果是奇数。从后面的栈中获取元素。
8、将当前节点值放到list中。依次将非空的右子树，左子树节点放到前面栈中。
9、for循环结束。计数+1.list加入到lists中
10、返回lists
时间复杂度：O（n），所有节点遍历一次。空间复杂度：O（n）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        //用linklist，整个作为队列遍历树，前半部分看成栈1，后半部分看成栈2.做到每一层的节点依次放到不同栈中。
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root); //开始从前面进前面出
        int count = 0;  //计数。从偶数开始
        while (!queue.isEmpty()) {    //队列用来遍历树
            int size = queue.size();   //获取当前层的元素个数
            List<Integer> list =  new ArrayList<>();
            for (int i = 0; i < size; i++) { //遍历当前层所有节点
                if (count%2 == 0) { //偶数，从前面栈中取元素。并分别将左子节点和右子节点放到后面栈中
                    TreeNode first = queue.pollFirst();
                    list.add(first.val);
                    if (first.left != null) queue.addLast(first.left);
                    if (first.right != null) queue.addLast(first.right);
                } else {    //奇数，从后面栈中取元素。并分别将右子节点和左子节点放到前面栈中
                    TreeNode right = queue.pollLast();
                    list.add(right.val);
                    if (right.right != null) queue.addFirst(right.right);
                    if (right.left != null) queue.addFirst(right.left);
                }
            }
            count++;    //计数+1
            lists.add(list);    //list添加到总list中
        }
        return lists;
    }
}

104.二叉树的最大深度

引言：
力扣上很多树的题目都是可以用递归很快地解决的，而这一系列递归解法中蕴含了一种很强大的递归思维：对称性递归(symmetric recursion)
什么是对称性递归？就是对一个对称的数据结构（这里指二叉树）从整体的对称性思考，把大问题分解成子问题进行递归，即不是单独考虑一部分(比如树的左子树)，而是同时考虑对称的两部分(左右子树)，从而写出对称性的递归代码

题型分类：
可以用对称性递归解决的二叉树问题大多是判断性问题(bool类型函数),这一类问题又可以分为以下两类：

1、不需要构造辅助函数。

这一类题目有两种情况：第一种是单树问题，且不需要用到子树的某一部分(比如根节点左子树的右子树)，只要利用根节点左右子树的对称性即可进行递归。第二种是双树问题，即本身题目要求比较两棵树，那么不需要构造新函数。该类型题目如下

2、需要构造辅助函数。

这类题目通常只用根节点子树对称性无法完全解决问题，必须要用到子树的某一部分进行递归，即要调用辅助函数比较两个部分子树。形式上主函数参数列表只有一个根节点，辅助函数参数列表有两个节点。该类型题目如下：

求二叉树最大深度
特殊判断：空树的最大深度为0
返回值：树非空，那么最大深度就是左子树最大深度和右子树最大深度的较大者加上根节点的1

代码如下：

int height(TreeNode*root)
{
    if (!root)
        return 0;
    else
        return max(height(root->left), height(root->right)) + 1;
}

110.平衡二叉树

定义函数 height，用于计算二叉树中的任意一个节点 p的高度：

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

计算某个节点的子树高度[常用函数]

/**
     * 某个节点的子树高度
     * @param root
     * @return
     */
    public int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }

二叉树判定代码：

public boolean isBalanced(TreeNode root) {
        boolean res = false;
        if (root == null)
            return true;
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right)){
            res = true;
        }
        return res;
    }

199.二叉树的右视图

1.BFS
思路：利用 BFS 进行层次遍历，记录下每层的最后一个元素。
时间复杂度： O(N)，每个节点都入队出队了 1 次。
空间复杂度： O(N)，使用了额外的队列空间。

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            res.add(queue.peek().val);
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                if (tmp.right != null)
                    queue.offer(tmp.right);
                if (tmp.left != null)
                    queue.offer(tmp.left);
            }
        }
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i)+"\t");
        }
        return res;
    }

2.DFS
思路：我们按照「根结点 -> 右子树 -> 左子树」的顺序访问，就可以保证每层都是最先访问最右边的节点的。

（与先序遍历「根结点 -> 左子树 -> 右子树」正好相反，先序遍历每层最先访问的是最左边的节点）

时间复杂度： O(N)O(N)，每个节点都访问了 1 次。
空间复杂度： O(N)O(N)，因为这不是一棵平衡二叉树，二叉树的深度最少是 logNlogN, 最坏的情况下会退化成一条链表，深度就是 NN，因此递归时使用的栈空间是 O(N)O(N) 的。

 public List<Integer> rightSideViewByDfs(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root,res,0);// 从根节点开始访问，根节点深度是0
        return res;
    }
    public void dfs(TreeNode root,List<Integer> res,int depth){
        if (root == null)
            return;
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (res.size() == depth){
            // 如果当前节点所在深度还没有出现在res里，
            // 说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            res.add(root.val);
        }
        System.out.println(res.size()+"\t"+root.val+"\t"+depth);
        depth++;
        dfs(root.right,res,depth);
        dfs(root.left,res,depth);
    }

226.翻转二叉树

1.递归
我们在做二叉树题目时候，第一想到的应该是用递归来解决。
仔细看下题目的输入和输出，输出的左右子树的位置跟输入正好是相反的，于是我们可以递归的交换左右子树来完成这道题。
看一下动画就明白了：

Leetcode刷题技巧 - 图18

其实就是交换一下左右节点，然后再递归的交换左节点，右节点
根据动画图我们可以总结出递归的两个条件如下：

终止条件：当前节点为 null 时返回
交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点

时间复杂度：每个元素都必须访问一次，所以是 O(n)O(n)
空间复杂度：最坏的情况下，需要存放 O(h)O(h) 个函数调用(h是树的高度)，所以是 O(h)O(h)
代码实现如下：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //递归函数的终止条件，节点为空时返回
        if(root==null) {
            return null;
        }
        //下面三句是将当前节点的左右子树交换
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        //递归交换当前节点的 左子树
        invertTree(root.left);
        //递归交换当前节点的 右子树
        invertTree(root.right);
        //函数返回时就表示当前这个节点，以及它的左右子树
        //都已经交换完了
        return root;
    }
}

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

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

动态图如下：

Leetcode刷题技巧 - 图19

深度优先遍历和广度优先遍历，从动画图中看起来很类似，这是因为演示的树层数只有三层。
时间复杂度：同样每个节点都需要入队列/出队列一次，所以是 O(n)O(n)
空间复杂度：最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是 n/2个，所以时间复杂度是 0(n)0(n)
代码实现如下：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) {
            return null;
        }
        //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //每次都从队列中拿一个节点，并交换这个节点的左右子树
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            //如果当前节点的左子树不为空，则放入队列等待后续处理
            if(tmp.left!=null) {
                queue.add(tmp.left);
            }
            //如果当前节点的右子树不为空，则放入队列等待后续处理
            if(tmp.right!=null) {
                queue.add(tmp.right);
            }
        }
        //返回处理完的根节点
        return root;
    }
}

解题思路
本文将会讲解为什么这道题适合用广度优先搜索（BFS），以及 BFS 适用于什么样的场景。

DFS（深度优先搜索）和 BFS（广度优先搜索）就像孪生兄弟，提到一个总是想起另一个。然而在实际使用中，我们用 DFS 的时候远远多于 BFS。那么，是不是 BFS 就没有什么用呢？

如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。这就是本文要介绍的两个场景：「层序遍历」、「最短路径」。

本文包括以下内容：

DFS 与 BFS 的特点比较
BFS 的适用场景
如何用 BFS 进行层序遍历
如何用 BFS 求解最短路径问题

DFS 与 BFS
让我们先看看在二叉树上进行 DFS 遍历和 BFS 遍历的代码比较。

DFS 遍历使用递归：
让我们先看看在二叉树上进行 DFS 遍历和 BFS 遍历的代码比较。
DFS 遍历使用递归：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS 遍历使用队列数据结构：

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

只是比较两段代码的话，最直观的感受就是：DFS 遍历的代码比 BFS 简洁太多了！这是因为递归的方式隐含地使用了系统的栈，我们不需要自己维护一个数据结构。如果只是简单地将二叉树遍历一遍，那么 DFS 显然是更方便的选择。
虽然 DFS 与 BFS 都是将/二叉树的所有结点遍历了一遍，但它们遍历结点的顺序不同。

这个遍历顺序也是 BFS 能够用来解「层序遍历」、「最短路径」问题的根本原因。下面，我们结合几道例题来讲讲 BFS 是如何求解层序遍历和最短路径问题的。

BFS 的使用场景总结：层序遍历、最短路径问题

BFS 的应用一：层序遍历

BFS 的层序遍历应用就是本题了：
LeetCode 102. Binary Tree Level Order Traversal 二叉树的层序遍历（Medium）

什么是层序遍历呢？简单来说，层序遍历就是把二叉树分层，然后每一层从左到右遍历：

乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

那么，怎么给 BFS 遍历的结果分层呢？我们首先来观察一下 BFS 遍历的过程中，结点进队列和出队列的过程：

截取 BFS 遍历过程中的某个时刻：

可以看到，此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们无法区分队列中的结点来自哪一层。
因此，我们需要稍微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 nn（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。

可以看到，在 while 循环的每一轮中，都是将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。
最终我们得到的题解代码为：

public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return null;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                TreeNode t = queue.remove();
                System.out.println(i);
                tmp.add(t.val);
                if (t.left != null)
                    queue.add(t.left);
                if (t.right != null)
                    queue.add(t.right);
            }
            res.add(tmp);
        }
        return res;
    }

左/右节点谁先入栈？

右节点先入栈：前序遍历（入栈顺序：右左中，出栈顺序：中左右）
左节点先入栈：后序遍历（入栈顺序：中右左，出栈顺序：左右中）