Leetcode Answers 199

继续刷题,能刷多少是多少。第199题又是一道涉及到BFS的题,而且和之前第102题如此之像。。。

题目:
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
4
5
1 <---
/ \
2 3 <---
\ \
5 4 <---

You should return [1, 3, 4].

思路:
这道题又是涉及到了二叉树,而且是求右侧的样子,那么第一反应就是right.right.right下去就好了。然而看例子,如果没有那个4,就变成了[1, 3, 5]而且这个5是root.left下面的。极端一点,让一个right都没而全是left的时候,从右边看过去也就是root.left.left这样下去了。那么从右边看过去,代表什么意思呢?回到102题的思路,Level Order Traversal,那其实每一个Level的最后一个Node就是我们想要求的内容。于是就很简单了,code和102题的也基本一样,只是稍作改动,不再向List中添加每一个level的list,而是改为添加每个Level的List的最后一个元素就好了,可以用System.Linq的Last()扩展方法,也可以反着添加,从右往左添加,这样只要添加每一个list[0]就可以了。后一种我还没测试,只贴前一种方法。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList<int> RightSideView(TreeNode root) {
var ret = new List<int>();
if(root != null){
var tempList = new List<int>();
var q = new Queue<TreeNode>();
q.Enqueue(root);
q.Enqueue(null);
TreeNode temp = null;
while(q.Count > 0){
temp = q.Dequeue();
if(temp != null){
if(temp.left != null) q.Enqueue(temp.left);
if(temp.right != null) q.Enqueue(temp.right);
tempList.Add(temp.val);
}else{
if(q.Count == 0){
ret.Add(tempList.Last());
break;
}else{
q.Enqueue(null);
ret.Add(tempList.Last());
tempList = new List<int>();
}
}
}
}
return ret;
}
}

考察:后面还有一道题,是要求一个二叉树的周长view,那个的底边并不一样,但是左右两边和这个是一样的,只是需要把右边的list给reverse一下。至于底边用pre-order求出来从root到每一个leaf的list,然后再把所有的list.Last()取出来大概就可以了吧。等做到那的时候再看看吧。

以上。

17-04-23
@Sturbridge