Leetcode-199-right view of binary tree

# LeetCode-199- Right side view of binary tree

Given a binary tree , Imagine yourself on the right side of it , In order from top to bottom , Returns the value of the node as seen from the right .

Example 1：

 Input : [1,2,3,null,5,null,4]
 Output : [1, 3, 4]
 explain :

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

Copy

# Their thinking

Method 1、Queue iteration +BFS：

According to the idea of sequence traversal , Using a Queue To iterate , Add the right node first when traversing the sequence , Traverse the binary tree in the order of right and left roots

The node visible on the right is always the first pop-up node in the queue during sequence traversal , namely i==0 when , Add nodes to res in

Method 2、DFS：

We do a depth first search on the tree , During search , We always visit the right subtree first . So for each floor , The first node we see on this floor must be the rightmost node . thus , You only need to store the first node of each deep access

# Java Code 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                if(i==0){
                    res.add(queue.peek().val);
                }
                TreeNode temp = queue.poll();
                if(temp.right!=null){
                    queue.add(temp.right);
                }
                if(temp.left!=null){
                    queue.add(temp.left);
                }
            }
        }
        return res;
    }
}

Copy

# Java Code 2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null) return res;
        DFS(root,0);
        return res;
    }

    public void DFS(TreeNode root,int depth){
        if(root==null) return;
        //  If the depth of the current node does not appear in res in 
        //  It indicates that the current node is the first accessed node at this depth , So add the current node to res in .
        if(depth>=res.size()){
            res.add(root.val);
        }
        DFS(root.right,depth+1);
        DFS(root.left,depth+1);
    }
}

Copy