Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

這題是求二叉樹的右視圖；我第一個想法就是用bfs呀，跟binary tree level order traversal那題一樣的套路就行了，而bfs二叉樹我已經(jīng)爛熟于心了。快速地寫了一下果然一次AC了。

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int curNum = 1;
        int nextNum = 0 ; 
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curNum -- ; 
            
            if (node.left!=null){
                queue.offer(node.left);
                nextNum ++ ; 
            }

            if (node.right!=null){
                queue.offer(node.right);
                nextNum ++ ;
            }
            
            if (curNum==0){
                res.add(node.val);
                curNum = nextNum ; 
                nextNum = 0 ;
            }
        }
        return res ; 
    }

晚上回來看看dfs之類的其他解法吧。上班去了。

下班回來了..

現(xiàn)在是晚上10:40分了，感覺也沒干什么突然間就這么晚了。。六點半去健身，健身完了磨蹭了一下去吃了個飯九點才回家，回來做了一組腹肌訓(xùn)練然后洗澡，就十點多了。。有點煩啊。以后我決定中午去健身了，然后晚上早點回。

回到正題，剛才用dfs寫了一下，還是模仿的binary tree level order traversal的dfs寫法，dfs函數(shù)像這樣：

    private void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> list) {
        if (root == null) return;
        if (level >= list.size()) {
            list.add(new ArrayList<Integer>());
        }
        list.get(level).add(root.val);
        dfs(root.left, level + 1, list);
        dfs(root.right, level + 1, list);
    }

這么做需要O(n)的Space，因為需要把每一行的元素都存起來然后讀每個sublist的最后一個元素。

然后我去看了leetcode高票答案，果然有奇淫巧技。。如下：

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
        
    }
}

乍一看有點難以理解，跟dfs幾乎一樣，但是不同的是它每次先遍歷右子樹，然后遍歷左子樹，然后把每層traverse到的第一個元素的val保存起來?？臻g復(fù)雜度O(logN)。

同理，左視圖的話，就把這左右child 遞歸的順序換一下位置就好了。

我就在想，既然如此是不是不需要遍歷左子樹了。。當然不行了，因為遇到只有l(wèi)eft child的node的時候無法進入下一層呀。比如下面的case就不行。

Input:
[1,2]
Output:
[1]
Expected:
[1,2]

dfs（遞歸）跟tree結(jié)合真是非常完美，兩者都有層的概念。

那么，今天就到這里了。晚安。