leetcode刷题总结 python版

leetcode 199. Binary Tree Right

2019-07-06  本文已影响0人  PJCK

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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路:
这个题可以用BFS,只要把BFS的队列中添加左子树和右子树中,先加右子树,而且可以设置一个变量,用于统计添加次数,保证每行能够加到最右边的结点的值。

python代码:

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

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        nums = []
        Q = []
        if not root:
            return []
        Q.append(root)
        while len(Q):
            length = len(Q)
            i = 0
            for i in range(length):
                T = Q[0]
                Q.pop(0)
                i += 1
                if i == 1:
                    nums.append(T.val)
                if T.right:
                    Q.append(T.right)
                if T.left:
                    Q.append(T.left)
        return nums

对了 ,如果对于写C++代码是很熟悉的话,可能会不经意的写i++,但是,这个在python上是错误的,应该用i+=1

上一篇下一篇

猜你喜欢

热点阅读