由二叉树的右视图（Leetcode.199）带来的进一步学习

题目：

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

实例：

思路：

使用BFS进行层次遍历，将每一层的最后遍历到的节点（即当层最右的节点）存入链表输出。

代码实现：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.add(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            for(int i = 0; i < levelSize; i++){
                TreeNode node = que.poll();
                if(node.left != null) {
                    que.add(node.left);
                }
                if(node.right != null) {
                    que.add(node.right);
                }
                if(i == levelSize-1){
                    list.add(node.val);
                }
            }
        }
        return list;
    }
}

思考：

a.Queue<TreeNode> que = new LinkedList<TreeNode>(); 这一句代码，我之前写的时候，有时候我会写成这样：b.List<TreeNode> que = new LinkedList<TreeNode>();，或是这样：c.LinkedList<TreeNode> que = new LinkedList<TreeNode>();。这种细节的地方我没有关注到，其实这是因为对API不熟悉和对多态的理解不充分导致的。

1. 为什么要写成a或b，而不是c？
面向对象三特性，“继承，多态，封装”，多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口，使用不同的实例而执行不同操作。
List是一个接口，而这个接口下面有多个实现类，包括Arraylist，Stack，Vector，LinkedList等。List对象可以调用父类和子类共有的方法，执行的是子类的方法，不可调用子类特有的方法，如果要调用子类特有的方法就需要下转型。
此时对象为父类的对象，子类的实例化，等号左边为编译时类型，右边为运行时类型。(在程序未运知行时道que只能当做List类型，在程序运行时JVM会把容que当做ArrayList类型。）
这种操作满足了依赖倒置原则。程序要尽量依赖于抽象，不依赖于具体。在需要修改子类类型的时候，如直接修改LinkedList为Arraylist即可，因为一个接口多种实现，在换一种实现的时候修改的地方很少。这种操作也满足了里氏代换原则。

向下转型：

    Son p1 = (Son)p;
    System.out.println(a instanceof Son);//true
    System.out.println(a instanceof Father);//true

里氏代换原则:
任何基类出现的地方子类一定可以出现。该原则可以降低程序的耦合性。

2. 什么时候要写成a，什么时候要写成b？
因为LinkedList同时继承了Deque和Collection接口，例如LinkedList中的offer()和add()就是分别实现的这两个接口中定义的方法，功能是很相似的（除了为空时，若调用该方法，offer()会返回false，add()会报错）。习惯是根据情境选择想要创建对象的接口。并使用对应实现的方法。

回顾：

二叉树的最大深度（Leetcode.104）一题的BFS解法的思路非常相似。

private static int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            maxDepth++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.pollFirst();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return maxDepth;
    }