1 // 我的代码
 2 package Leetcode;
 3 /**
 4  * 199. Binary Tree Right Side View
 5  * address: https://leetcode.com/problems/binary-tree-right-side-view/
 6  * Given a binary tree, imagine yourself standing on the right side of it, 
 7  * return the values of the nodes you can see ordered from top to bottom.
 8  * 
 9  */
10 import java.util.*;
11 
12 public class BinaryTreeRightSideView {
13     public static void main(String[] args) {
14         TreeNode[] tree = new TreeNode[9];
15         for (int i = 1; i < 9; i++){
16             tree[i] = new TreeNode(i);
17         }
18         TreeNode.link(tree, 1, 2, 3);
19         TreeNode.link(tree, 2, 4, 5);
20         TreeNode.link(tree, 3, 6, -1);
21         TreeNode.link(tree, 5, 7, 8);
22         // 先序遍历
23         TreeNode.prePrint(tree[1]);
24         // solution
25         List<Integer> result = rightSideView(tree[1]);
26         System.out.println(result);
27         
28         // solution2
29         List<Integer> result2 = rightSideView2(tree[1]);
30         System.out.println(result2);
31         
32     }
33     /**
34      * 方法一：时间复杂度较高，需要 O(n),n为树中节点的个数
35      * @param root
36      * @return
37      */
38     public static List<Integer> rightSideView(TreeNode root) {
39         List<Integer> result = new ArrayList<>();
40         Queue<TreeNode> queue = new LinkedList<>();
41         int childNum = 0;
42             if (root != null){
43                 queue.offer(root);
44                 while(!queue.isEmpty()){
45                     TreeNode node = queue.poll(); 
46                     if(node.left!= null){
47                         queue.offer(node.left);
48                         childNum++;
49                     }
50                     if (node.right != null)
51                     {
52                         queue.offer(node.right);
53                         childNum++;
54                     }
55                     System.out.println("queue.size() = " + queue.size());
56                     if (childNum - queue.size() == 0){
57                         result.add(node.val);
58                         childNum = 0;
59                     }
60                 } 
61         }
62 
63         return result;
64         
65     }

 1 /**
 2      * 方法二
 3      * 别人家的解法，巧妙，速度快且好理解
 4      * @param root 
 5      * 中右左 深度优先遍历，保存每层的第一个节点。用当前结果表的size作为标识,这样保证每次存的节点都是第一次出现在该层的节点
 6      * @return
 7      */
 8     public   static List<Integer> rightSideView2(TreeNode root) {
 9         List<Integer> res = new ArrayList<Integer>();
10         if (root == null){
11             return res;
12         }
13         dfs (root, res, 0);
14         return res;
15     }
16     
17     public static void dfs (TreeNode root, List<Integer> res, int level){
18         if (root == null){
19             return;
20         }
21         if (res.size() == level){
22             res.add (root.val);
23         }
24         if (root.right != null){
25             dfs (root.right, res, level + 1);
26         }
27         if (root.left != null){
28             dfs (root.left, res, level + 1);
29         }
30     }