leetcode199 二叉树的右视图 DFS 与 BFS 解法

 　　两种解法，DFS 与 BFS ，均已通过。对于 DFS 来说，我们需要从右到左遍历所有节点，并在每次遍历时记录当前深度。如果当前深度与结果数组长度相同，则为该层可以右视到的节点：

    /**
     * @Author Nxy
     * @Date 2020/5/9
     * @Description DFS 解法
     */
    List<Integer> reList = new LinkedList<Integer>();

    public final List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return reList;
        }
        rightSideViewDFS(root, 0);
        return reList;
    }

    public final void rightSideViewDFS(TreeNode node, int depth) {
        if (depth == reList.size()) {
            reList.add(node.val);
        }
        if (node.right != null) {
            rightSideViewDFS(node.right, depth + 1);
        }
        if (node.left != null) {
            rightSideViewDFS(node.left, depth + 1);
        }
    }

　　对于 BFS ，我们逐层遍历，并将每层最右侧节点记录下来。这就要求我们在遍历时可以对二叉树分层，这里我采用了两个队列，每层的元素放在不同的队列中。像两个桶，不断的倒过来倒过去的对二叉树进行分层：

    /**
     * @Author Nxy
     * @Date 2020/5/9 
     * @Description BFS 解法
     */
    public final List<Integer> rightSideViewBFS(TreeNode root) {
        Queue<TreeNode> queue1 = new LinkedBlockingQueue<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedBlockingQueue<TreeNode>();
        List<Integer> reList = new LinkedList<Integer>();
        if(root==null){return reList;}
        queue1.add(root);
        while (queue1.size() != 0) {
            if (queue1.size() != 0) {
                TreeNode right = queue1.remove();
                addChildNodes(queue2,right);
                reList.add(right.val);
            }
            while (queue1.size() != 0) {
                TreeNode right = queue1.remove();
                addChildNodes(queue2,right);
            }
            if (queue2.size() != 0) {
                TreeNode right = queue2.remove();
                addChildNodes(queue1,right);
                reList.add(right.val);
            }
            while (queue2.size() != 0) {
                TreeNode right = queue2.remove();
                addChildNodes(queue1,right);
            }
        }
        return reList;
    }

    private void addChildNodes(Queue<TreeNode> queue,TreeNode node){
        if(node.right!=null){queue.add(node.right);}
        if(node.left!=null){queue.add(node.left);}
    }