[LeetCode]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, 3, 4]。

解题思路:

二叉树的层次遍历,每层按照从右向左的顺序依次访问节点

Python代码:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def rightSideView(self, root):
        ans = []
        if root is None:
            return ans
        queue = [root]
        while queue:
            size = len(queue)
            for r in range(size):
                top = queue.pop(0)
                if r == 0:
                    ans.append(top.val)
                if top.right:
                    queue.append(top.right)
                if top.left:
                    queue.append(top.left)
        return ans

 

本文链接:http://bookshadow.com/weblog/2015/04/03/leetcode-binary-tree-right-side-view/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论