Leetcode - Binary Tree Right Side View

My code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> view = new ArrayList<Integer>();
        if (root == null)
            return view;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode temp = q.poll();
                if (i == 0)
                    view.add(temp.val);
                if (temp.right != null)
                    q.offer(temp.right);
                if (temp.left != null)
                    q.offer(temp.left);
            }
        }
        return view;
    }
}

My test result:

Paste_Image.png

这道题目，没做出来。看了答案后，
感觉真的是，算法是融入在血液的。刷题，培养的，就是这么一种思想。
这种思想，我在zigzag中也碰到过。
真的是，随心所欲，不逾矩。
想法在心中，题目在变，想法不会变。
而我现在是，题目不变，想法在不断地变。无法找到准确的方法来分析题目。
看到一道题目，脑子还是一片空白。

这道题目，我怎么就没有想到，拿队列来做呢。然后采用zigzag的方式遍历。
http://www.programcreek.com/2014/04/leetcode-binary-tree-right-side-view-java/
看了这篇博客就懂了。

**
总结： queue来遍历tree
**

Anyway, Good luck, Richardo!

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if (root == null)
            return ret;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (i == 0) {
                    ret.add(curr.val);
                }
                if (curr.right != null)
                    q.offer(curr.right);
                if (curr.left != null)
                    q.offer(curr.left);
            }
        }
        return ret;
    }
}

不难。没什么好总结的。

Anyway, Good luck, Richardo!

我用的还是老方法。没什么好说的。
然后网上看到别人用了这个方法，感觉挺巧妙的。

Their code:

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);
        
    }
}

reference:
https://discuss.leetcode.com/topic/11768/my-simple-accepted-solution-java/2

感觉bfs 能做的，dfs都能做，只是需要有个容器来暂存状态。

Anyway,Good luck, Richardo! -- 09/07/2016