Binary Tree Right Side View

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.
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

1. 树的层次遍历
   层次遍历时优先右子树。

   def bfs(root):
   	view = []
   	que = deque([root, None])
   	while que[0] != None:
   		first = True
   		while que and que[0] != None:
   			node = que.popleft()
   			if first:
   				view.append(node.val)
   				first = False
   			if node.right:
   				que.append(node.right)
   			if node.left:
   				que.append(node.left)
   		que.popleft()
   		que.append(None)
   	return view
   
   def rightSideView(root):
   	if not root:
   		return []
   	return bfs(root)

访问每个节点一次，时间复杂度为O(n)，空间复杂度依赖于包含最多子节点的层级。最坏情况为满二叉树，此时有N/2+1，复杂度为O(n)

1. 深度优先遍历
   优先访问右子树，能保证到达该层的第一个节点一定是最右节点。
   从而对于每次遍历，记录高度，如果该高度尚未访问，更新即可。

   def rightFirstVisit(node, height, view):
   	if not node:
   		return
   	if len(view) < height:
   		view.append(node.val)
   	rightFirstVisit(node.right, height+1, view)
   	rightFirstVisit(node.left, height+1, view)
   
   def rightSideView2(root):
   	view = []
   	rightFirstVisit(root, 1, view)
   	return view

时间复杂度O(n)，空间复杂度为O(h)（结果集的大小)。
如果能事先知道树的高度，当访问到最深层时即可立刻终止。