Leetcode[199] Binary Tree Right Side View
16 Nov 2015###Task1 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].
###Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
ret = []
queue = []
queue.append(root)
while len(queue) > 0:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if i == size - 1:
ret.append(cur.val)
return ret
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int last = 0;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
last = cur.val;
}
list.add(last);
}
return list;
}
}
###Points
- Level order traversal