Leetcode/亚麻 -- 199. Binary Tree Right Side View (BFS + DFS)

199. Binary Tree Right Side View (BFS + DFS)
medium
https://leetcode.com/problems/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].

思路1： BFS, use level order traverlsal. key is to track each level size, and add the 1ast one to list.

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        if(root == null) return res;
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i = 0; i < size; i++){//traveling current level
                TreeNode curr = qu.remove();
                if(i == size - 1)res.add(curr.val);
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return res;
    }

思路2: DFS， preorder改一下顺序，从右走的左边. To ensure rightmost node of depth,
            Key is we ensure we only add the first node of the specific depth by check depth == list size.
for ex, if we add node at depth 1 from right subtree, we won't add it again when travel the left subtree

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