leecode 199. 二叉树的右视图

秒速五厘米 2023-01-17 03:13 161阅读 0赞

### 文章目录 ###

*  题目
 *  涉及知识点
 *   *  BFS,广度遍历
     *  DFS，深度遍历
 *  代码
 *  参考博客

# 题目 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]

# 涉及知识点 #

二叉树的**BFS,DFS 深度遍历跟广度遍历**

## BFS,广度遍历 ##

Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                if (node.left != null) { 
                    queue.add(node.left);
                }
                if (node.right != null) { 
                    queue.add(node.right);
                }
            }

## DFS，深度遍历 ##

Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                if (node.left != null) { 
                    rightSideView(node.left);
                }
                if (node.right != null) { 
                    rightSideView(node.right);
                }
            }

# 代码 #

public List<Integer> rightSideView(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> resultList = new ArrayList<>();
            queue.add(root);
            while(!queue.isEmpty()){ 
                int size = queue.size();
                for(int i =0;i<size;i++){ 
                    TreeNode node = queue.poll();
                    if(node.left!=null){ 
                        queue.add(node.left);
                    }
                    if(node.right!=null){ 
                        queue.add(node.right);
                    }
                    if (i == size - 1) { 
                    	//记录一行中的最后一个值
                        resultList.add(node.val);
                    }
                }
    
            }
    
            return resultList;
        }

# 参考博客 #

*  [java代码使用BFS和DFS遍历二叉树][java_BFS_DFS]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]: /images/20221022/98cbc6bcac4c41149d212a46941d80b1.png
[java_BFS_DFS]: https://blog.csdn.net/qq_37638061/article/details/89598413