LeetCode199. 二叉树的右视图

迈不过友情╰ 2022-05-09 05:44 149阅读 0赞

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

**示例:**

输入: [1,2,3,null,5,null,4]
    输出: [1, 3, 4]
    解释:
    
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

--------------------

思路：

![70][]

/**
     * 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<List<Integer>> res=bfs(root);
            List<Integer> list=new LinkedList<Integer>();
            for(List<Integer> l:res){
                list.add(l.get(l.size()-1));//取每一层的最后一个元素值
            }
            return list;
        }
        /**
         * 返回广度优先遍历每一层的结果
         * @param root
         * @return
         */
        public  List<List<Integer>> bfs(TreeNode root){
            List<List<Integer>> res=new LinkedList<List<Integer>>();
            if(null==root){
                return res;
            }
            ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
            queue.addLast(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> tmp=new LinkedList<Integer>();
                for(int i=0;i<size;i++){
                    TreeNode node=queue.removeFirst();
                    tmp.add(node.val);
                    if(null!=node.left){
                        queue.addLast(node.left);
                    }
                    if(null!=node.right){
                        queue.addLast(node.right);
                    }
                }
                res.add(tmp);
            }
            return res;
        }
    }

[70]: /images/20220509/b4ab42ac826f4daba5528ebdf6cb91d7.png