題目：

給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節(jié)點值。

實例：

思路：

使用BFS進行層次遍歷，將每一層的最后遍歷到的節(jié)點（即當層最右的節(jié)點）存入鏈表輸出。

代碼實現(xiàn)：

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>();。這種細節(jié)的地方我沒有關注到，其實這是因為對API不熟悉和對多態(tài)的理解不充分導致的。

1. 為什么要寫成a或b，而不是c？
面向對象三特性，“繼承，多態(tài)，封裝”，多態(tài)是同一個行為具有多個不同表現(xiàn)形式或形態(tài)的能力。多態(tài)就是同一個接口，使用不同的實例而執(zhí)行不同操作。
List是一個接口，而這個接口下面有多個實現(xiàn)類，包括Arraylist，Stack，Vector，LinkedList等。List對象可以調用父類和子類共有的方法，執(zhí)行的是子類的方法，不可調用子類特有的方法，如果要調用子類特有的方法就需要下轉型。
此時對象為父類的對象，子類的實例化，等號左邊為編譯時類型，右邊為運行時類型。(在程序未運知行時道que只能當做List類型，在程序運行時JVM會把容que當做ArrayList類型。）
這種操作滿足了依賴倒置原則。程序要盡量依賴于抽象，不依賴于具體。在需要修改子類類型的時候，如直接修改LinkedList為Arraylist即可，因為一個接口多種實現(xiàn)，在換一種實現(xiàn)的時候修改的地方很少。這種操作也滿足了里氏代換原則。

向下轉型：

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

里氏代換原則:
任何基類出現(xiàn)的地方子類一定可以出現(xiàn)。該原則可以降低程序的耦合性。

2. 什么時候要寫成a，什么時候要寫成b？
因為LinkedList同時繼承了Deque和Collection接口，例如LinkedList中的offer()和add()就是分別實現(xiàn)的這兩個接口中定義的方法，功能是很相似的（除了為空時，若調用該方法，offer()會返回false，add()會報錯）。習慣是根據(jù)情境選擇想要創(chuàng)建對象的接口。并使用對應實現(xiàn)的方法。

回顧：

二叉樹的最大深度（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;
    }