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.
Example:
Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
思路
DFS
每当recursion一进入到next level，
就立马加上该level的right side node到result里
对应的，
在recursion的时候，先处理 root.right
代码
1 class Solution { 2 public List<Integer> rightSideView(TreeNode root) { 3 List<Integer> result = new ArrayList<>(); 4 if(root == null) return result; 5 dfs(root, result, 0); 6 return result; 7 } 8 9 private void dfs(TreeNode root, List<Integer> result, int level ){ 10 // base case 11 if(root == null) return; 12 /*height == result.size() limits the amount of Node add to the result 13 making sure that once go to the next level, add right side node to result immediately 14 */ 15 if(level == result.size()){ 16 result.add(root.val); 17 } 18 // deal with right side first, making sure right side node to be added first 19 dfs(root.right, result, level+1); 20 dfs(root.left, result, level+1); 21 } 22 }
思路
BFS（iteration）
每次先将right side node 加入到queue里去
保证 当i = 0 的时候，poll出来的第一个item是right side node
代码
1 public List<Integer> rightSideView(TreeNode root) { 2 // level order traversal 3 List<Integer> result = new ArrayList(); 4 Queue<TreeNode> queue = new LinkedList(); 5 // corner case 6 if (root == null) return result; 7 8 queue.offer(root); 9 while (!queue.isEmpty()) { 10 int size = queue.size(); 11 for (int i = 0; i< size; i++) { 12 TreeNode cur = queue.poll(); 13 // make sure only add right side node 14 if (i == 0) result.add(cur.val); 15 // add right side node first, making sure poll out first 16 if (cur.right != null) queue.offer(cur.right); 17 if (cur.left != null) queue.offer(cur.left); 18 } 19 } 20 return result; 21 }
转载于:https://www.cnblogs.com/liuliu5151/p/9820365.html
相关资源：数据结构—成绩单生成器