【LeetCode】199. Binary Tree Right Side View 解题报告（Python）

标签： LeetCode

---

题目地址：https://leetcode.com/problems/binary-tree-right-side-view/description/

题目描述：

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].

题目大意

打印出二叉树每层的最右边的元素。

解题方法

这个题就是102. Binary Tree Level Order Traversal翻版啊！上个题是要直接打印每层的元素，这个是要每层元素的最右边元素，所以可以使用之前的解法，然后再把每层的给取出来嘛～～

递归解法：

# 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]

        """

        res = []

        self.levelOrder(root, 0, res)

        return [level[-1] for level in res]

    def levelOrder(self, root, level, res):

        if not root: return

        if len(res) == level: res.append([])

        res[level].append(root.val)

        if root.left: self.levelOrder(root.left, level + 1, res)

        if root.right: self.levelOrder(root.right, level + 1, res)

非递归解法，使用队列。

这个解题的技巧在于，queue其实也可以用[-1]直接找到这个层的最后一个元素。

每次进行while循环，都是开始了新的一层，for循环的巧妙在于，直接遍历队列中已有的元素，也就是上层的元素。这样的话就直接把上层的遍历完了，新的层也加入了队列。

# 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]

        """

        res = []

        if not root: return res

        queue = collections.deque()

        queue.append(root)

        while queue:

            res.append(queue[-1].val)

            for i in range(len(queue)):

                node = queue.popleft()

                if node.left:

                    queue.append(node.left)

                if node.right:

                    queue.append(node.right)

        return res

日期

2018 年 3 月 14 日 –霍金去世日