subject

Ideas

1. I've done a problem to distinguish each layer of binary tree traversal before , This problem should be based on that , Just add the rightmost node of each layer to the returned list . I wrote it directly AC. Look at the problem solution, which belongs to the solution of breadth first traversal , Then let's look at the solution of depth first traversal .

Code （BFS）

    public List<Integer> rightSideView(TreeNode root) {
    
        List<Integer> ans = new ArrayList<>();
        // Create a queue 
        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        while(!que.isEmpty()){
    
            // The length of the current layer 
            int size = que.size();
            // Each floor comes out together 
            for(int i=0;i<size;i++){
    
                TreeNode temp = que.remove();
                if(i== size-1){
     // The last words   Need to add ans
                    ans.add(temp.val);
                }
                // Enter it around the child 
                if(temp.left!=null) que.add(temp.left);
                if(temp.right!=null) que.add(temp.right);
            }
        }
        // return ans
        return ans;
    }

Code （DFS）

    List<Integer> ans = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
    
        // The root is traversed from right to left   It can ensure that the node on the right is traversed first 
        // Need to maintain a depth To determine whether to join ans
        DFS(root,0);
        return ans;
    }
    public void DFS(TreeNode root,int depth){
    
        if(root==null) return;
        // If at present depth and ans equal   Note No depth The nodes of the layer have not been added ans
        // And as root right left traversal   At this time root It must be the rightmost node and should be added 
        if(depth==ans.size()) ans.add(root.val);
        // Continue traversing 
        DFS(root.right,depth+1);
        DFS(root.left,depth+1);
    }