1. 前言

除了可以直接使用递归处理的二叉树问题，二叉树中还有一些典型的算法问题，需要和其他的数据结构配合解决，例如使用堆、栈以及队列数据结构配合查找的过程，可以避免使用递归算法。

2. 二叉树视图

2.1 二叉树右视图

面试官提问：给定一颗二叉树，求出从二叉树右边看到的所有节点结果集合。

题目解析：

求解二叉树右视图问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/binary-tree-right-side-view/。

首先给出二叉树右视图的定义：从二叉树的右边看到的第一个节点，即是当前层数的结果节点，把所有的结果节点添加到集合，即是结果集合。

举例来说，对于上图中的二叉树结果，其右视图的结果集是[3,20,8]。

根据题意，最明显的方法是层次遍历二叉树，也就是BFS广度优先搜索算法，按照这个思路。

我们使用双向队列作为数据结构存储层次遍历的结果，我们要解决两个问题，一是如何实现层次遍历，二是如何判断是否是每层的最右边的节点。

（1）初始条件：首先把根节点放入双向队列尾部；
（2）最右判断：每次首先得到双向队列当前的长度 size，这是一个固定值，对于第一层来说，因为只有一个根节点，所以 size-1 的位置就是最右边的节点；
（3）循环处理：以size作为循环次数，从双向队列头部开始，不断弹出节点，将每个节点的非空左右子树加入双向队列尾部。当遍历到 size-1 的位置时，就是当前层数的最右节点。一直循环，直到双向队列为空，即处理完所有的二叉树节点。

在 Java中 使用 ArrayDeque 数据结构实现双向队列，下面给出 Java 算法的源码以及注解，示例：

public List<Integer> rightSideView(TreeNode root) {
	Queue<TreeNode> q= new ArrayDeque<>();
    List<Integer> res = new ArrayList<>();
	//如果是空节点，直接返回空结果集
    if(root == null) 
    	return res;
    //将根节点添加到队列
    q.offer(root);
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i< size; i++){
        	//从双向队列头部弹出第一个节点
            TreeNode node = q.poll();
            //如果是当前层数的最后一个节点，就是需要的右视图节点
            if(i == size-1) 
          		res.add(node.val);
          	//弹出节点的有效左节点加入队列
            if(node.left != null) 
            	q.offer(node.left);
            //弹出节点的有效右节点加入队列
            if(node.right != null) 
            	q.offer(node.right);
        }
    }
    //返回结果集
    return res;
}

当然除了 BFS 算法外，本题目也可以使用 DFS 算法，即通过前序遍历获取需要的最右节点，这里不再赘述。

2.2 二叉树左视图、二叉树层次遍历

求解二叉树左视图、二叉树右视图、二叉树层次遍历问题，都可以使用双向队列求解。

（1）二叉树右视图：每次获取当前层双向队列的最后一个节点；
（2）二叉树左视图：每次获取当前层双向队列的第一个节点；
（3）二叉树层次遍历：对于每遍历一次 size ，结果添加到一个单独的列表。

3. 小结

候选人在学习算法问题时，需要注意举一反三，目前算法网站的面试题题库已经接近 2000 题，如果企图通过刷遍题库的方式提高算法能力，是非常消耗精力的。所以要做到精简问题和总结算法套路，例如本章中介绍的二叉树和双向队列配合使用，实现广度优先搜索，就是一个非常典型的算法模板，可以多加熟悉。