【LeetCode-中等题】199. 二叉树的右视图

题目

方法一：层序遍历取每一层最后一个元素

// 方法一 ：层序 + 集合(取每层子集合最后一个元素)// List<List<Integer>> Rlist = new ArrayList<>();// public List<Integer> rightSideView(TreeNode root) {//     if(root == null ) return new ArrayList<>();//     Queue<TreeNode> queue = new ArrayDeque<>();//     queue.offer(root); //     while(!queue.isEmpty()){//         int count = queue.size();//         List<Integer> res = new ArrayList<>();//         for(int i=0;i<count;i++){//             TreeNode node = queue.poll();//             res.add(node.val);//         if(node.left != null) queue.offer(node.left);//         if(node.right != null) queue.offer(node.right);//         }//         Rlist.add(res);//每层节点集合加入到大集合//     }//       List<Integer> result = new ArrayList<>();//结果集//     for(List list : Rlist ){//         result.add((Integer)list.get(list.size()-1));//取每层集合最后一个元素//     }//     return result;// }
// 方法一（优化） ：在层序遍历的时候直接要每一层的最后一个元素加入集合  就不需要把一层所有节点的加入集合再去取每层集合最后一个了public List<Integer> rightSideView(TreeNode root) {List<Integer> Rlist = new ArrayList<>();//结果集if(root == null ) return Rlist;Queue<TreeNode> queue = new ArrayDeque<>();queue.offer(root); while(!queue.isEmpty()){int count = queue.size();for(int i=0;i<count;i++){TreeNode node = queue.poll();if(i == count -1)//只取一层最后一个元素（count）Rlist.add(node.val);if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);}}return Rlist;}

方法二：深度优先搜索

根 右 左 的顺序 取每层第一个被访问到的节点（depth == list.size()）

   List<Integer> result = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {dfs(root,0);//起始递归 root  深度为0return result;}public void dfs(TreeNode tree ,int  depth){if(tree == null) return ;if(depth == result.size()) result.add(tree.val);//若当前深度 = 集合的大小，说明在该层还没加入任何元素，此时只需加入第一次访问的元素就行dfs(tree.right,depth+1);//切换到下一层继续找第一次访问的元素dfs(tree.left,depth+1);//切换到下一层继续找第一次访问的元素}