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 <---
题意：
给定一个二叉树，
想象自己站在二叉树的右侧
返回所有能看到的node(返回的node的order是从上往下)
思路：
dfs，
使其访问顺序为： root --> right --> left
这样访问nodes为：10, 15, 20, 12, 5, 7, 9, 2
用一个level来维护每层关系, 便于把每层最右侧nodes取出来，放入result中
则：（10,0), (15,1), (20,2), (12,2), (5,1), (7,2), (9,3), (2,2)
每次一到达新的level，根据root --> right --> left的访问顺序，该新level最先被访问的node一定是最右侧view 需要输出的node。将其加入result中。
（10,0), (15,1), (20,2), (12,2), (5,1), (7,2), (9,3), (2,2)
result输出： 10， 15， 20， 9
代码：
1 public class BinaryTreeRightSideView { 2 public List<Integer> rightSideView(TreeNode root) { 3 List<Integer> result = new ArrayList<>(); 4 // corner case 5 if (root == null) return result; 6 dfs(root, result, 0); 7 return result; 8 } 9 10 public void dfs(TreeNode root, List<Integer> result, int level) { 11 //recursion 的base case 12 if (root == null) { 13 return; 14 } 15 if (level == result.size()) { 16 result.add(root.val); 17 } 18 19 dfs(root.right, result, level + 1); 20 dfs(root.left, result, level + 1); 21 22 } 23 }
转载于:https://www.cnblogs.com/liuliu5151/p/9114744.html
相关资源：数据结构—成绩单生成器