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 Solution 1:
# 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 []
l = [root]
res = []
while l:
res.append(l[-1].val)
r = []
for node in l:
if node.left: r.append(node.left)
if node.right: r.append(node.right)
l = r
return res
Python Solution 2:
# 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 []
def preorder(root, res, level):
if level == len(res):
res.append(root.val)
if root.right: preorder(root.right, res, level + 1)
if root.left: preorder(root.left, res, level + 1)
res = []
preorder(root, res, 0)
return res
Summary:
- Solution 2 is DFS, beautiful.
LeetCode: 199. Binary Tree Right Side View
近期评论