199. Binary Tree Right Side View

题目描述

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.

For example:
Given the following binary tree,

   1            
<
---
 /   \
2     3         
<
---
 \     \
  5     4       
<
---

You should return[1, 3, 4].解题方法

解题方法

BFS:

 level order ->聯想到BFS

 儲存每層的最後element

DFS:

 從右邊traverse -> 如果list.size\(\)跟"level"一樣，則儲存下來   

//level order ->聯想到BFS
//儲存每層的最後element
    /*public List<Integer> rightSideView(TreeNode root){
        //corner case
        if(root == null){
            return new ArrayList<Integer>();
        }

        List<Integer> lists = new ArrayList<>();            //we always add the last element: O(1)
        Queue<TreeNode> queue = new LinkedList<>();         //FIFO
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }

                if(i == size - 1){
                    lists.add(node.val);
                }
            }
        }

        return lists;
    }*/

    //DFS
    //從右邊traverse -> 如果list.size()跟"level"一樣，則儲存下來
    public List<Integer> rightSideView(TreeNode root){
        List<Integer> lists = new ArrayList<>();
        //corner case
        if(root == null){
            return lists;
        }

        rightSideView(root, lists, 0);
        return lists;
    }

    //overloadding : compile time determine
    private void rightSideView(TreeNode root, List<Integer> lists, int level){
        if(root == null){
            return;
        }
        if(lists.size() == level){
            lists.add(root.val);
        }
        rightSideView(root.right, lists, level + 1);
        rightSideView(root.left, lists, level + 1);
    }