|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.LinkedList; |
| 5 | +importjava.util.List; |
| 6 | +importjava.util.Queue; |
| 7 | + |
| 8 | +importclasses.TreeNode; |
| 9 | + |
| 10 | +/**199. Binary Tree Right Side View |
| 11 | +
|
| 12 | + Total Accepted: 50496 |
| 13 | + Total Submissions: 138613 |
| 14 | + Difficulty: Medium |
| 15 | +
|
| 16 | +Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. |
| 17 | +
|
| 18 | +For example: |
| 19 | +Given the following binary tree, |
| 20 | +
|
| 21 | + 1 <--- |
| 22 | + / \ |
| 23 | +2 3 <--- |
| 24 | + \ \ |
| 25 | + 5 4 <--- |
| 26 | +
|
| 27 | +You should return [1, 3, 4]. */ |
| 28 | +publicclassBinaryTreeRightSideView { |
| 29 | +//Using BFS is pretty straightforward. But there might be a smarter way. |
| 30 | +publicList<Integer>rightSideView(TreeNoderoot) { |
| 31 | +List<Integer>res =newArrayList<Integer>(); |
| 32 | +if(root ==null)returnres; |
| 33 | +Queue<TreeNode>q =newLinkedList<TreeNode>(); |
| 34 | +q.offer(root); |
| 35 | +while(!q.isEmpty()){ |
| 36 | +intcurrentSize =q.size(); |
| 37 | +inti =0; |
| 38 | +for(;i <currentSize-1;i++){ |
| 39 | +TreeNodecurrentNode =q.poll(); |
| 40 | +if(currentNode.left !=null)q.offer(currentNode.left); |
| 41 | +if(currentNode.right !=null)q.offer(currentNode.right); |
| 42 | +} |
| 43 | +TreeNodecurrentNode =q.poll(); |
| 44 | +if(currentNode.left !=null)q.offer(currentNode.left); |
| 45 | +if(currentNode.right !=null)q.offer(currentNode.right); |
| 46 | +res.add(currentNode.val); |
| 47 | +} |
| 48 | +returnres; |
| 49 | +} |
| 50 | + |
| 51 | +publicstaticvoidmain(String...strings){ |
| 52 | +BinaryTreeRightSideViewtest =newBinaryTreeRightSideView(); |
| 53 | +TreeNoderoot =newTreeNode(1); |
| 54 | +root.left =newTreeNode(2); |
| 55 | +root.right =newTreeNode(3); |
| 56 | +root.left.right =newTreeNode(5); |
| 57 | +root.right.right =newTreeNode(4); |
| 58 | +List<Integer>result =test.rightSideView(root); |
| 59 | +for(inti :result){ |
| 60 | +System.out.print(i +", "); |
| 61 | +} |
| 62 | +} |
| 63 | +} |