https://leetcode.com/problems/binary-tree-right-side-view/

 

又是一道tree的题。还是两种方法，第一种递归(recursion)，使用上面遍历树的模板。这道题其实就是优先找到右子树的节点，没有右子树则找到左子树，因此递归的时候需要带上层级level，另外，采用先右节点，再左节点的方式遍历该树，需要确保第一个节点(优先右节点，没有右节点则为左节点)被加入到最后的结果中。

public List<Integer> rightSideView(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        dfsHelper(root, res, 0);
        return res;
    }
    
    private void dfsHelper(TreeNode root, List res, int level) {
        // 如果right为null，则遍历left，否则前序遍历right
        if (root != null) {
            if (res.size() == level) res.add(root.val); //makes sure the first element of that level will be added to the result list
            dfsHelper(root.right, res, level + 1);  // checks the RIGHT node first and then the LEFT
            dfsHelper(root.left, res, level + 1);
        }
    }

如果采用iteration，则按照每个层级的顺序去遍历该树，发现只需要添加每一个层级遍历的最后一个节点到树。例如：

 

按照层级遍历， 0 –> [1]  1 -> [2, 3]   2-> [5, 4]

左视图为[1,3,4]，即为每一层级的最后一个节点。

使用队列作为辅助数据结构，算法实现如下:

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();  // 初始化队列
        if (root == null) return res;           
        q.offer(root);                           
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (curr.left != null) q.offer(curr.left);
                if (curr.right != null) q.offer(curr.right);
                if (i == size - 1) res.add(curr.val);    // 该层级的最后一个节点加到队列中去
            }
        }
        return res;
    }